题目传送门:https://codeforces.com/problemset/problem/803/C
题目大意:
给定两个数\(n,k\),求\(k\)个数\(a_1,满足\(\sum\limits_{i=1}^ka_i=n\),且使得\(\gcd\limits_{i=1}^k\{a_i\}\)最大
假定\(\alpha=\gcd\limits_{i=1}^k\{a_i\}\),则有\(a_i=\alpha\times r_i\),因为\(\sum\limits_{i=1}^kr_i\geqslant \frac{k(k+1)}{2}\),故\(\alpha\leqslant \frac{2n}{k(k+1)}\)
显然\(n=\alpha\sum\limits_{i=1}^kr_i\),故\(\alpha\)应为\(n\)的约数,且最大不超过\(\frac{2n}{k(k+1)}\)
故我们可以\(O(\sqrt n)\)找到最大的\(\alpha\),然后按照\(r_i=i(1\leqslant i\leqslant k-1)\),\(r_k=\frac{n}{\alpha}-\sum\limits_{i=1}^{k-1}r_i\)构造\(a_i\)即可
/*program from Wolfycz*/
#include