CF803C Maximal GCD 讲解

zrl123456 · 2024-01-12 18:54:23 · 题解

题目
相信很多人是被数据范围劝退的 \dots\dots
数据范围为：

你可能觉得输出 10^{10} 个数是不可能的事情。
但是我们思考一下：
都知道高斯的求和公式吧：

因为 (1+1.5\times 10^5)(1.5\times 10^5)/2>10^{10}， 所以当 k\ge 1.5\times 10^5 的时候， 直接输出 -1 就可以了。
上述行为是为了防止爆 long long， 再次特判， 若 k(k+1)/2>n， 则依然输出 -1。
然后我们设序列的第 i 个数为 a_i， 最大公约数为 m， 根据同余定理， 不难得到：

所以， 我们需要找出 n 的全部因数， 从大到小排个序， 做完上述步骤后的时间复杂度为 O(\sqrt n+k\log_2k)，简化为 O(k\log_2 k)， 是可承受的。
下一步我们枚举 a_i， 直到找到符合 a_i\times (k(k+1)/2)\le n 条件的数， 最后输出即可， 此处的复杂度仅仅只有 O(\sqrt n+k)。
代码：

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[100005],summ,maxn;
bool cmp(long long x,long long y){ return x>y; }
void work(){
    for(long long i=1;i*i<=n;i++)
        if(n%i==0)
            if(i*i==n) a[++summ]=i;
            else{
                a[++summ]=i;
                a[++summ]=n/i;
            }
    return;
}
int main(){
    cin>>n>>k;
    if(k>=150000){
        cout<<-1;
        return 0;
    }
    if((1+k)*k/2>n){
        cout<<-1;
        return 0;
    }
    work();
    sort(a+1,a+summ+1,cmp);
    for(int i=1;i<=summ;i++)
        if(n*2/k/(k+1)>=a[i]){
            maxn=a[i];
            break;
        }
    for(int i=1;i<k;i++){
        cout<<i*maxn<<' ';
        n-=i*maxn;
    }
    cout<<n;
    return 0;
}