本文共 862 字，大约阅读时间需要 2 分钟。

题目链接：

题目大意：

       给出两个数n和m，你需要找到一个长度为n的序列a，使其满足 a1+a2+…+aN = M，找到a1,a2,…,aN 的gcd的最大可能值

题解：

      我们假设gcd为g，那么一定满足m=gt(t是正整数)，又因为a1+a2+…+aN = M，所以a1=gt1, a2=gt2 ,....., an=gtn (t1,t2,...,tn都是正整数)，也就是说m=g(t1+t2+t3+...+t4),而(t1+t2+t3+...+t4)至少>=n

        所以我们如果能找到一个数i，使m%i==0 && m/i>=n ，那么x就是一个符合的gcd值，找最大的x即可

 

需要注意的是，这个题的m是1e9

      一开始我写的是for(int i=1;i<=m;++i) ,TLE了。后来想了一下i肯定<=m/n

       就改成 for(int i=1;i<=m/n;++i) ,仍然有一个点过不了，T掉，当n很小的时候的确有这种可能

      于是反正我们是找最大的值，那么就倒过来，从大到小循环 for(int i=m/n;i>=1;--i)，找到第一个符合条件的就输出然后break就行了，因为这一定是最大的i

#include
   
    #include
    
     #include
     
      #include
      
       #define ll long long#define INF 1000000007using namespace std;int main(){    //freopen("input.txt","r",stdin);    int n,m;    cin>>n>>m;    int ans=0;    for(int i=m/n;i>=1;--i)    {        if(m%i==0)        {            int g=m/i;            if(g>=n)                return cout<
       <
      
     
    
   

转载地址：http://pkfgf.baihongyu.com/