小G的约数

题目链接:nowcoder 218398

到主站看:https://blog.csdn.net/weixin_43346722/article/details/114603257

题目大意

定义 F(n) 是 n 的约数的和,然后 G(n) 则是 1~F(n) 的和。
然后问你 G(G(n)) 是多少。

思路

首先,我们会想到,暴力算是不行的。

然后我们考虑优化算 怎么弄。
我们先看约数有什么特别的地方,那有约数,又有前缀和,那如果对于一个数 ,它会是哪些数的因子呢?
,也就是会有多少个数含有这个因子)

但是你会想到,就算你每次只枚举因子,你还是会超时。

然后你会从整除向下取整想到一个叫做整除分块的东西。
然后你会想到在一个块中,它的 都是一样的,然后因子的大小是每次加一。
那这就是一个等差序列,可以 搞。
那块的个数是 ,那时间就过去了。

代码

#include<cstdio>
#define ll long long

using namespace std;

ll n;

ll g(ll now) {//求 G(n)
    ll re = 0;
    for (ll i = 1; i <= now; i++) {
        ll r = now / (now / i);//整除分块确定右边界
        re += (now / i) * (i + r) * (r - i + 1ll) / 2;
        i = r;
    }
    return re;
}

int main() {
    scanf("%lld", &n);

    printf("%lld", g(g(n)));

    return 0;
}