Codeforces 803C. Maximal GCD

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

中了若干trick之后才过...

　　k个数的严格递增序列最小权值和就是${n*(n+1)/2}$,枚举这些数字增加的倍数x,使得序列变成${x,2x,3x...kx}$，然后再使最后一个数字变大满足要求就可以了，枚举的复杂度是根号$n$的。

　　要注意枚举倍数$x$的时候还要顺便枚举了$n/x$,然后${n*(n+1)/2}$这个东西是会爆long long的。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<cstring>
 8 using namespace std;
 9 #define maxn 10010
10 #define llg long long 
11 #define LDB long double
12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
13 llg n,m,cha,k;
14 
15 inline int getint()
16 {
17        int w=0,q=0; char c=getchar();
18        while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
19        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
20 }
21 
22 llg find(llg x)
23 {
24     llg up=sqrt(x),Ans=-1;
25     for (llg i=1;i<=up;i++)
26         if (x%i==0)
27         {
28             if ((LDB)x*2/(LDB)i/(LDB)k>=(LDB)(k+1) && i>Ans) {Ans=i; cha=x/i-(k*(k+1))/2;}
29             if ((LDB)i*2/(LDB)k>=(LDB)(k+1) && x/i>Ans) {Ans=x/i; cha=i-(k*(k+1))/2;}
30         }
31     return Ans;
32 }
33 
34 int main()
35 {
36     yyj("C");
37     cin>>n>>k;
38     llg val=find(n);
39     if (val==-1) {cout<<-1; return 0;}
40     for (llg i=1;i<k;i++) printf("%lld ",i*val);
41     printf("%lld",(k+cha)*val);
42     return 0;
43 }