剛開始一直沒有看懂這個題目的意思赠幕，看了很久才明白。題目的意思就是給你兩個數(shù)n和k询筏，然后讓你干下面這些事情榕堰。
- 構(gòu)造一個k位嚴格遞增的序列。
- 序列和為n
- 同時使得這個序列的最大公約數(shù)最大、
這題畢竟關(guān)鍵的就是求這個最大公約數(shù)q逆屡，因為序列和為n圾旨，也就是q(1+2+3+......k-1+k)<=n。顯然q也是n的一個因數(shù)魏蔗，通過這樣的方法就可以求得最大共約數(shù)了砍的，不過要注意如果直接遍歷n的話是會超時的，因為有1e+10那么大莺治，通過對n開方可以將循環(huán)次數(shù)減少到sqrt(n)最大也就是1e+5就不會超時了廓鞠。如果qsum_K-1小于n就將所有的都加到最后也該數(shù)里面去，這里注意不要類加q*(1+2+.....+k-1)這樣會爆的谣旁，去掉q累加就可以了床佳，我就犯了這個錯誤。
具體代碼如下：
#include <iostream>
#include<cmath>
using namespace std;
typedef long long LL;
LL n, k;
void caculate()
{
if (k>141420)
{
cout << "-1" << endl;
return;
}
LL sum_k = (k + 1)*k / 2;
LL q = 0;
LL sqr=sqrt(n);
for (long long i = 1; i <= sqr; i++)
{
if (n%i == 0)
{
if (i >= sum_k)
{
q = n / i; break;
}
else if (n / i >= sum_k)
q = i;
}
}
if (!q)
{
cout << "-1" << endl;
return;
}
LL sum = 0;
for (LL i = 1; i < k; ++i)
{
cout << i*q << ' ';
sum += i;
}
cout << q*(n / q - sum) << endl;
return;
}
int main()
{
while (cin >> n >> k)
{
caculate();
}
return 0;
}
原文：http://blog.yinaoxiong.cn/2017/08/01/Maximal-GCD.html
本作品由尹傲雄采用知識共享署名-非商業(yè)性使用-相同方式共享 4.0 國際許可協(xié)議進行許可榄审。
