题目链接
http://codeforces.com/contest/803/problem/C
题意
给一个数n和一个数k，要求把n分成k个数
a1,a2,...ak
的和，并且这k个数严格递增，并且使划分出来的这k个数的GCD最大，求划分方案。
思路
a1+a2+...+ak=n
假设其最大的gcd为x，那么就有：
x⋅p1+x⋅p2+...+x⋅pk=n
极端情况是
p1
到
pk
依次是
1,2,3,...,k
我们设
y=p1+p2+...+pk
，那么就有
y≥k⋅(k+1)2
如果
y>k⋅(k+1)2
，那么这k数就是：
1，2，3，...，y−(1+2+3+...+k−1）
所以，我们只需要枚举
n
的因子x，并且找到最大的那个
x
使nx≥k⋅(k 1)2即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL n, k;
void print(
int x) {
LL y = n / x;
for (
int i =
1; i <= k -
1; i++) {
cout << x * i <<
' ';
y -= i;
}
cout << x * y << endl;
exit(
0);
}
int main() {
scanf(
"%I64d%I64d", &n, &k);
if (k >=
1e6 || (k <
1e6 && k * (k +
1) /
2 > n))
cout << -
1 << endl;
else {
vector<int> v1, v2;
long long y = k * (k +
1) /
2, x =
1;
for (LL i =
1; i <=
sqrt(n); i++) {
if (n % i ==
0) {
v1.push_back(i);
v2.push_back(n / i);
}
}
for (
int i =
0; i < v2.size(); i++) {
x = v2[i];
if (n / x >= y) {
print(x);
}
}
for (
int i = v1.size() -
1; i >=
0; i--) {
x = v1[i];
if (n / x >= y) {
print(x);
}
}
}
return 0;
}
