AC日记——Maximal GCD codeforces 803c

803C - Maximal GCD

思路:

  最大的公约数是n的因数;

  然后看范围k<=10^10;

  单是答案都会超时;

  但是,仔细读题会发现,n必须不小于k*(k+1)/2;

  所以,当k不小于10^5时直接-1就好;

  我们可以构造出gcd为1的序列为

    1,2,3,4……n-k+1;

  然后一个个枚举n的因子p;

    1*p,2*p,3*p……(n-k+1)*p;

  当枚举的p使得序列不满足于严格递增时,结束,输出合法答案;

来,上代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define ll long long long long n,k; int main()
{
cin>>n>>k;
if(k==)
{
cout<<n;
return ;
}
if(n<k||k>||k==)
{
cout<<-;
return ;
}
long long c=k*(k+)/;
if(n<c)
{
cout<<-;
return ;
}
ll p=n/c,last=;
for(ll i=;i<=sqrt(n)+;i++)
{
if(n%i) continue;
ll ok=,sum=n;
for(ll j=;j<k;j++)
{
sum-=j*i;
if(sum<=j*i) ok=false;
}
if(sum<=i*(k-)) ok=false;
if(ok) last=i;
else break;
}
for(ll i=sqrt(n)+;i>=;i--)
{
if(n%i) continue;
ll a=n/i;
ll ok=,sum=n;
for(ll j=;j<k;j++)
{
sum-=j*a;
if(sum<=j*a) ok=false;
}
if(sum<=a*(k-)) ok=false;
if(ok) last=a;
else break;
}
ll sum=n;
for(ll i=;i<k;i++) printf("%lld ",i*last),sum-=i*last;
printf("%lld",sum);
return ;
}
上一篇:Codeforces H. Maximal GCD(贪心)


下一篇:快排 快速排序 qsort quicksort C语言