zcmimi's blog
avatar
zc
2020-09-14 16:15:00
  • 本文总阅读量
查看原题

点击跳转

从大到小枚举n的因子x

如果能够满足那么x+2x+\dots+kx\le n

x(1+2+\dots+k)\le n\\ \dfrac{xk(1+k)}{2}\le n\\ xk(1+k)\le 2n

其中x\le \dfrac{2n}{k(1+k)}

找到最大的x后,按顺序输出x,2x,\dots+(k-1)x,最后一个数为n减去前面的数的和

#include<bits/stdc++.h>
typedef long long ll;
int main(){
    ll n,k;scanf("%lld%lld",&n,&k);
    ll l=n*2/k/(k+1),sqr=sqrt(n),x=1;
    if(!l)return puts("-1"),0;
    for(ll i=1;i<=sqr&&i<=l;++i)if(n%i==0){
        ll t=n/i;x=i;
        if(t<=l){x=t;break;}
    }
    for(;x;--x)if(n%x==0){
        for(ll now=x;n>=now*2+x&&--k;now+=x)
            printf("%lld ",now),n-=now;
        return printf("%lld\n",n),0;
    }
}
LG CF803C Maximal GCD
comment评论
Search
search