【codeforces 803C】Maximal GCD

时间：2023-03-09 17:21:50
【codeforces 803C】Maximal GCD

【题目链接】:http://codeforces.com/contest/803/problem/C

【题意】



给你一个数字n;一个数字k;

让你找一个长度为k的序列;

要求这个长度为k的序列的所有数字的和为n;

且这k个数字的最大公因数最大;

【题解】



key:这个最大公因数一定是n的因子！

/*

    设最后选出来的k个数字为

    a[1],a[2]...a[k];

    这些数字的最大公因数为g

    g*b[1],g*b[2],...g*b[k]

    n=g*b[1]+g*b[2]+...+g*b[k];

    这里g必然是n的因子;

    且

    n/g==b[1]+b[2]+..+b[k]>=1+2+3...+k···①

    (1+2+3..+k 是最小的满足严格递增的长度为k的序列)

    构造最后的答案为

    1*g,2*g,3*g...(k-1)*g以及n-(1+2+3..k-1)*g

    前k-1项肯定是递增的;

    而由①式可知

        n-g*(1+2+3..+k)>=0

        则

        最后一项=n-g*(1+2+3..+k-1)>=g*k

    所以也是单调递增的;

    这里只要保证①式成立,就肯定能找到解了

    (1+2+...+k如果大于1e10直接输出无解就好,这样防止爆LL)

    有解就从大到小枚举n的因子,找到第一个符合的输出就好

*/

【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 110;

LL n,k;

vector <LL> v1,v2;

void out(LL g)

{

    LL temp = 0;

    for (int i = 1;i <= k-1;i++)

        cout <<i*g<<' ',temp+=i*g;

    cout << n-temp<<endl;

    exit(0);

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use

    cin >> n >> k;

    if (k>=1e6)

        return cout << -1 << endl,0;

    LL sumk = (1+k)*k/2;

    LL ma = sqrt(n);

    for (LL g = 1;g <= ma;g++)

        if (n%g==0)

            v1.pb(g),v2.pb(n/g);

    int len = v2.size();

    rep1(i,0,len-1)

    {

        LL x = v2[i];

        if (n/x>=sumk)

            out(x);

    }

    len = v1.size();

    rep2(i,len-1,0)

    {

        LL x = v1[i];

        if (n/x>=sumk)

            out(x);

    }

    cout << -1 << endl;

    return 0;

}

相关文章