「CF803C」 Maximal GCD

题目链接

\(Solution\)

令\(gcd\)为\(x\),那么我们将整个序列\(/x\),则序列的和就变成了\(\frac{n}{x}\),所以\(x\)必定为\(n\)的约数所以现在就是要构造出一个序列长度为\(k\),和为\(\frac{n}{x}\)。我们令前\(k-1\)个为\(1,2....k-1\)最后一个再用\(\frac{n}{x}-\)这\(k-1\)个的和就是最后一个数了。最后的答案就是构造出来的序列\(*x\)

所以我们现在就是要来判断\(x\)可不可行，很明显如果\((1+k)*k/2>\frac{n}{x}\)的话显然不可行，反之则可以。所以我们找到最大的\(x\)用上述方法构造即可.

注意特判一下\(k\)很大的时候，有可能会乘爆

\(Code\)

#include<bits/stdc++.h>

#define int long long

#define rg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

using namespace std;

int read(){

    int x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();

    return f*x;

}

int n,k,maxx,ans;

bool check(int x){

	return (1+k)*k/2<=(n/x);

}

main(){

	n=read(),k=read();

	if(k>2e5) puts("-1"),exit(0);

	for(int i=1;i*i<=n;i++){

		if(n%i!=0) continue;

		if(check(i)) maxx=max(maxx,i);

		if(check(n/i)) maxx=max(maxx,n/i);

	}

	if(!maxx) puts("-1"),exit(0);

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

		cout<<i*maxx<<" ",ans+=i*maxx;

	cout<<n-ans;

    return 0;

}

巴特西

「CF803C」 Maximal GCD

题目链接

\(Solution\)

\(Code\)

最新文章

热门文章