[AHOI2005]约数研究
[AHOI2005]约数研究
首先，我们可以分别统计每一个数作为约数所做的贡献，加起来即可。
也即：
[displaystylesum_{i=1}^n{ndiv i}
]
这样就是(O(n))的了，据说还可以用什么“数论分块”，也不知道怎么用。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
int main()
{
scanf("%d", &n);
int ans;
for(int i = 1; i <= n; ++ i) ans += n / i;
printf("%d
", ans);
return 0;
}
当然，还有其他想法。比如：
对于一个数(k)，将它拆分成(p*q)，其中(p)为最小质因子，那么有：
[f[i*prime[j]]=f[i] * 2 (prime[j]>vis[i])
]
[f[i*prime[j]]=f[i]*(cnt[i]+2)/(cnt[i]+1)
]
于是TLE。
不过有一个神仙做法：https://www.cnblogs.com/xzz_233/p/8365414.html
不知道为什么。