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} $那就自己去看高斯求和吧！
代码
#include#define int long longusing namespace std;const int N=1e5+10;int n,k,a,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 分享、互助 让互联网精神温暖你我 yyds。多谢分享 懂技术并乐意极积无私分享的人越来越少。珍惜 谢谢分享，试用一下 很好很强大我过来先占个楼 待编辑 感谢分享 懂技术并乐意极积无私分享的人越来越少。珍惜 这个好，看起来很实用 收藏一下 不知道什么时候能用到 yyds。多谢分享 新版吗？好像是停更了吧。 感谢发布原创作品，程序园因你更精彩 感谢，下载保存了 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 很好很强大我过来先占个楼 待编辑 感谢分享，学习下。 不错，里面软件多更新就更好了 谢谢分享，试用一下 这个好，看起来很实用
页:
[1]
2