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 ;

}

巴特西

AC日记——Maximal GCD codeforces 803c

最新文章

热门文章