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