C、小G的约数题解

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);
}