【16届蓝桥杯寒假刷题营】第2期DAY5

2.最大公因数 - 蓝桥云课

问题描述

给你2个正整数N，M。

你需要构造一个有N个数的正整数序列a，满足以下条件：

• ∑i=1N​ai​=M。

求gcd(a)，可能的最大值。

输入描述

输入一行两个正整数N，M，表示数组的长度和数组元素总和。

输出描述

输出一行，表示答案。

输入格式

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;
vector<ll>v;
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()
{cin>>n>>m;gene(n,m);if(m % n == 0)//如果能整除 cout << m / n;//那么这就是最大公因数 elsecout << v[v.size()-1];//最大的因子就是最大公因数 return 0;
}