[CF803C] Maximal GCD（gcd，贪心，构造）

题目链接：http://codeforces.com/contest/803/problem/C

题意：k个单增的数和为n，求这k个数gcd最大。

很好特判的一点是∑i，i from 1 to k如果大于n的话，很明显是不能构造的。所以特判一发，结果k*(k+1)/2爆LONG LONG TLE了一发QAQ。

设a1 a2 ... ak为解，那么a1+a2+...+ak=n，设gcd(a1,a2...,ak)=p，那么a1=p*b1,a2=p*b2...ak=p*bk。

那么gcd(b1,b2,...,bk)=1。且p*(b1+b2+...+bk)=n，那么n%p=0，说明他们的gcd p为n的因数。

首先处理出所有n的因数。

这样有一个很o_O的构造，反正b1 b2他们的gcd是1，不如让他们从头到尾开始排，前k-1个分别是1~k-1，因为不能重复，则特判第k项是否大于k-1就行了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 LL n, k;
 6 vector<LL> p;
 7 
 8 bool ok(LL v) {
 9     LL m = n / v;
10     LL sum = (1 + (k - 1)) * (k - 1) / 2;
11     if(m - sum >= k) {
12         for(LL i = 1; i < k; i++) printf("%I64d ", i * v);
13         printf("%I64d
", v * (m - sum));
14         return 1;
15     }
16     return 0;
17 }
18 
19 int main() {
20     // freopen("in", "r", stdin);
21     while(~scanf("%I64d%I64d",&n,&k)) {
22         if(k+1 > 2 * n / k) {
23             puts("-1");
24             continue;
25         }
26         p.clear();
27         for(LL i = 1; i*i <= n; i++) {
28             if(n % i == 0) {
29                 p.push_back(i);
30                 p.push_back(n/i);
31             }
32         }
33         sort(p.begin(), p.end());
34         p.erase(unique(p.begin(), p.end()), p.end());
35         bool flag = 0;
36         for(int i = p.size() - 1; i >= 0; i--) {
37             if(ok(p[i])) {
38                 flag = 1;
39                 break;
40             }
41         }
42         if(!flag) puts("-1");
43     }
44     return 0;
45 }