C. Maximal GCD
time limit per test
memory limit per test
input
output
n. You should create such strictly increasing sequence of k positive numbers a1, a2, ..., ak, that their sum is equal to n
Greatest common divisor of sequence is maximum of such numbers that every element of sequence is divisible by them.
-1.
Input
n and k (1 ≤ n, k ≤ 1010).
Output
k numbers — resulting sequence. Otherwise output -1. If there are multiple answers, print any of them.
Examples
input
6 3
output
1 2 3
input
8 2
output
2 6
input
5 3
output
-1
遍历n的所有约数，找到最大的约数m,满足 i = n / m 使得(k+1)*k/2<=i
那么约数m就是数列的最大公约数
#include <bits/stdc++.h>
#define maxn 100005
typedef long long ll;
using namespace std;
bool judge(ll i, ll k) {
if((k+1) <= 2*i/k)
return true;
return false;
}
int main() {
//freopen("in.txt", "r", stdin);
ll n, k, maxs = 0;
scanf("%I64d %I64d", &n, &k);
for(ll i = 1; i * i <= n; i++) {
if(n % i == 0) {
ll m = n / i;
if(judge(m, k))
maxs = max(i, maxs);
if(judge(i, k))
maxs = max(m, maxs);
}
}
if(maxs == 0) {
puts("-1");
return 0;
}
ll cnt = 1;
ll m = n / maxs;
int first = 0;
for(int i = 1; i <= k; i++) {
if(first)
putchar(' ');
if(i != k)
printf("%I64d",cnt * maxs);
else{
cnt--;
printf("%I64d",(m - (1+cnt)*cnt/2) * maxs);
}
cnt++;
first = 1;
}
return 0;
}