Maximal GCD
题目链接:http://codeforces.com/contest/803/problem/C
——每天在线，欢迎留言谈论。
题目大意：
给你n,k(1<=n,k<=1e10)。
要你输出k个数，满足以下条件：
①这k个数之和等于n
②严格递增
②输出的 这k个数 的最大公约数q是同样满足①②条件中的最大的！
思路：
一、先找出这个符合条件的最大的q：
①q一定是n的 公约数
②q*(1+2+···+k)<=n 时的q就可以成为共约数(因为输出时 只需要把k增大到m,m满足 1+2+··+(k-1)+m=n/q 就可以)
③在n的公约数中从大到小遍历是否符合条件即可。
↓ ↓ ↓ ↓ 不超时的一种 遍历公约数 的思想！
只需要通过for(long long i=1;i<sqrt(n);i++)来找出最大的那个q
假如2是他的一个约数，那么n/2也是。3是的话n/3也是。所以循环到sqrt(n)即可。最多1e5次循环 不会超T。
二、输出这k个数
q*a1，q*a2，q*a3 ······ q*ak（没有，号，只是好看）
其中的{a1,a2,a3···ak}={1，2，3 ··· (k-2) , (k-1) , ((n/q)- sum)}(sum=1+2+···+(k-1))
PS注意：k好大时 long long 也装不下(1+2+···+k)!（不说太清楚，自己体会，哈哈...）
AC代码：
#include <iostream>
#include <cmath>
using namespace std;
int main()
{//1<=n,k<=1e10
long long n,k,sqr,cadd,q;//q为最大公约数
cin>>n>>k;
if(k>)
{
cout<<"-1"<<endl;return ;
}
cadd=(+k)*k/;sqr=sqrt(n);q=;
for(long long i=;i<=sqr;i++)
{
if(n%i==)
{
if(i>=cadd)
{q=n/i;break;}
else if(n/i>=cadd)
q=i;
}
}
//cout<<q<<endl;
if(!q)
{
cout<<"-1"<<endl;return ;
}
long long sum=,i;
for(i=;i<k;i++)
{
cout<<i*q<<" ";sum+=i;
}
cout<<q*(n/q-sum)<<endl;
return ;
}
2017-05-04 14:06:58 -> 2017-05-05 12:51:05 -> 2017-05-05 20:45:26