网站设计费 建设费入什么科目,河北邯郸邮编,git网站开发,泰安服装网站建设2.最大公因数 - 蓝桥云课
问题描述
给你2个正整数N#xff0c;M。
你需要构造一个有N个数的正整数序列a#xff0c;满足以下条件#xff1a;
∑i1NaiM。
求gcd(a)#xff0c;可能的最大值。
输入描述
输入一行两个正整数N#xff0c;M#xff0c;表示数组的长…2.最大公因数 - 蓝桥云课
问题描述
给你2个正整数NM。
你需要构造一个有N个数的正整数序列a满足以下条件
∑i1NaiM。
求gcd(a)可能的最大值。
输入描述
输入一行两个正整数NM表示数组的长度和数组元素总和。
输出描述
输出一行表示答案。
输入格式
19 189 114514
输出格式
2
评测数据范围
1≤N≤M≤109
思路
如果m/n可以整除那么这个m/n就是最大公因数因为平均分配了。如果不可以整除那么需要求出1~m/n的整数最大因子这就是最大公因数。
代码如下
#include bits/stdc.h
using namespace std;
typedef long long ll;
ll n,m;
vectorllv;
void gene(ll n,ll m)
{for(ll i 1 ;i m/n ; i)//寻找1到k/m的所有整数因子 {if(m % i 0){v.push_back(i);}}
}
int main()
{cinnm;gene(n,m);if(m % n 0)//如果能整除 cout m / n;//那么这就是最大公因数 elsecout v[v.size()-1];//最大的因子就是最大公因数 return 0;
}
