C、小G的约数
前置知识:整除分块https://blog.csdn.net/weixin_45419138/article/details/103446724
G(n)为约数和的和
最大值n=50000,可以先用朴素方法把F(N)表打出来,即求出每一个数的因子和,复杂度为O(nsqrt(n))
发现n=50000时,G(n)=2056198403,G(G(n))显然是无法暴力求解的
我们开始探索一个数与其因子的关系和性质来简化运算
对于一个数x,他必为x,2x,3x,.....的因子
似乎有规律可循,对于上限n,数x的计算次数便为n/x
如n=10,1的计算次数为10/1=10(f(1)、f(2)、f(3)...含有1因子),2的计算次数为10/2=5(f(2)、f(4)、f(6)...含有2因子),3的计算次数为10/3=3(f(3)、f(6)、f(9)含有3因子)
因此我们发现每个因子的计算次数与n的整除分块大小相等,而整除分块求和的时间复杂度为O(sqrt(n)),满足题目范围。
因此在求解整除分块的过程中,将因子对答案的贡献×该数出现次数即为答案
整除分块求解的过程中需要对因子跳跃时的数字求和,可以记录上一次的因子,用两个等差数列求和公式相减即可,如因子从6跳到10,需要对6,7,8,9,10这种等差数列求和,即S(10)-S(5)。
可能描述比较难懂,中间数据已注释,可去掉注释符观察中间数据加以理解
#include<bits/stdc++.h> using namespace std; long long n, ans; int main() { scanf("%d", &n); long long t=-1,t2; for(long long l = 1, r;l <= n; l = r+1) { r = n/(n/l); // 区间最右边 //printf("%d %d %d\n",r,(n/l),(r-l+1)); //因子,因子贡献次数,因子跳跃的大小 if(t==-1) t2=r; else t2=r*(r+1)/2-t*(t+1)/2; ans += t2*(n/l) ; //printf("%d %d\n",t2,ans);//跳跃的因子的求和 答案 t=r; } //printf("%lld\n", ans); long long aans=0; t=-1; for(long long l = 1, r;l <= ans; l = r+1) { r = ans/(ans/l); // 区间最右边 //printf("%d %d %d\n",r,(n/l),(r-l+1)); if(t==-1) t2=r; else t2=r*(r+1)/2-t*(t+1)/2; aans += t2*(ans/l) ; //printf("%d %d\n",t2,ans); t=r; } printf("%lld\n", aans); }