小G的约数

题目

小G定义了两个函数，F(n) 为 n 的约数和，G(n) 为 F(1)+F(2)+...+F(n-1)+F(n)
小G想知道 G(G(n)) 等于多少

解题思路

遍历 1 到 n，其中约数为 i 的数的个数是 n/i。
所以，。

long long G(int x){
    long long ans = 0;
    for(int i=1; i<=x; ++i){
        long long t = x/i;
        ans += t*i;
    }
    return ans;
}

上面的代码会超时，使用整除分块来实现。

C++代码

#include<iostream>
using namespace std;

long long G(int x){
    long long ans = 0;
    long long le = 1;
    long long ri;
    while(le <= x){
        long long t = x/le;
        ri = x/t;
        ans += t*(le+ri)*(ri-le+1)/2;    // 在 [1,x] 中，约数为 i 的数有 t 个，其中 i 是 [le,ri] 范围中的数
                                         // 故，ans += t * (le + (le+1) + (le+2) + ... + ri)
        le = ri+1;
    }
    return ans;
}

int main(){
    int n;
    cin >> n;
    cout << G(G(n)) << endl;
    return 0;
}