CF803C Maximal GCD做题笔记

题面描述

给你一个\(n\)和\(k\),让你构造一个长的为\(k\),且和为\(n\)的严格单调递增的序列，使其的序列gcd（最大的公共因子）最大。
思路解析

因为他的数据极其的大（\(1 \leq n, k \leq 10^{10}\)）所以我们只能使用\(O(1)\)或者是\(O(\sqrt{n})\)的（别问我为什么没有\(O(log n)\)）但是很明显他是不可能用\(O(1)\)写出来的，所以我们只能使用\(O(\sqrt{n})\)了。
既然时间复杂度定的差不多了，那想一想什么要用到\(\sqrt{n}\)呢？对啦，就是枚举\(n\)的因数，为什么是\(n\)呢？因为这个序列的gcd肯定是\(n\)的因数
证明很简单，设gcd为x,这个数列为b，则有：
\(\sum_{i = 1}^{k} b_i = \sum_{i = 1}^{k} x*\frac{b_i}{x} = x*\sum_{i = 1}^{k} \frac{b_i}{x} = n\)
所以我们可以预处理\(n\)的所有因子，然后进行构造一个严格递增上升序列每个项都乘上这个因子（语文不好，后面有代码）就可以了。
那我们就这剩下一个问题那就是怎么样会无解其实很简单：你的\(n\)要是比1,2,3....,k的和还小，那不就无解了吗，要是不会求$\sum_{i=1}^{k} $那就自己去看高斯求和吧！
代码

[code]#include#define int long longusing namespace std;const int N=1e5+10;int n,k,a[N],m;vector g;bool cmp(int x,int y){        return x>y;}signed main(){//        freopen(".in","r",stdin);//        freopen(".out","w",stdout);        cin>>n>>k;        if(n*2/k