【数学】codeforces C. Maximal GCD

http://codeforces.com/contest/803/problem/C

【题意】

给定两个数n,k(1 ≤ n, k ≤ 10^10)

要你输出k个数，满足以下条件：

①这k个数之和等于n

②严格递增

②输出的这k个数的最大公约数q尽可能大。

【思路】

因为是严格递增，所以sum[k]>=k(k+1)/2，而n<=1e10,所以k应该在1e5多一点。

可以找出最大的满足n<=1e10的k，给定的k超出这个直接输出-1.

然后接下来考虑怎么使最大公约数最大：

因为q肯定也是n的约数，所以可以先把n的公约数都找出来，时间复杂度是O(sqrt(n)),从大到小排序后一次判断能不能满足q*(1+2+···+k)<=n就可以了。

【注意】

1. 判断q*(1+2+···+k)<=n不能写if(q*sum[k]<=n)

会爆的，最大的q就是n本身，当n=1e10,k=1e5的时候，q*sum[k]就爆long long了，所以要写成

 if(sum[m]<=n/d[i])

     {

         return true;

     }

     return false;

2. 对于i*i==n的要特别判断

3. 要特别考虑1 1的corner case.

【Accepted】

 #include <iostream>

 #include <stdio.h>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <bitset>

 #include <ctime>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 ll n,m;

 const int maxn=1e6+;

 ll sum[maxn];

 int cou;

 void Init()

 {

     memset(sum,,sizeof(sum));

     for(int i=;i<maxn;i++)

     {

         sum[i]=sum[i-]+(ll)i;

         if(sum[i]>=)

         {

             cou=i;

             break;

         }

     }

 }

 ll d[];

 bool cmp(ll a,ll b)

 {

     return a>b;

 }

 bool judge(int i)

 {

     if(sum[m]<=n/d[i])

     {

         return true;

     }

     return false;

 }

 void Print(int i)

 {

     for(int k=;k<=m-;k++)

     {

         cout<<d[i]*(ll)k<<" ";

     }

     cout<<n-d[i]*sum[m-]<<endl;

 }

 int main()

 {

     Init();

     cin>>n>>m;

     if(m>=cou)

     {

         printf("-1\n");

         return ;

     }

     if(sum[m]>n)

     {

         printf("-1\n");

         return ;

     }

     int cnt=;

     ll index=;

     for(int i=;(ll)i*(ll)i<n;i++)

     {

         if(n%(ll)i==)

         {

             d[cnt++]=(ll)i;

             d[cnt++]=n/(ll)i;

         }

         index=(ll)i;

     }

     index++;

     if(index*index==n)

     {

         d[cnt++]=index;

     }

     sort(d,d+cnt,cmp);

     int flag=;

     for(int i=;i<cnt;i++)

     {

         if(judge(i))

         {

             flag=;

             Print(i);

             break;

         }

     }

     if(flag==)

     {

         printf("-1\n");

     }

     return ;

 }

注意爆ll,注意corner case

巴特西

【数学】codeforces C. Maximal GCD

最新文章

热门文章