求
其中0<N<=2^32
看起来是莫比乌斯反演,其实不是。。。。。。
化一波式子先
然后别化了(手动喷血
后面那个求和号不就是欧拉函数的定义么(手动喷血
然后变成了求
什么?枚举因子个数和求欧拉函数都是
注意到这里要求的都是N的因子的欧拉函数的值,因此可以对N质因数分解,然后直接用dfs枚举各质因子的次数来枚举因子,并且在dfs过程中能直接用欧拉函数的公式维护出欧拉函数值,然后复杂度就变成了O(因子的个数),也就是
代码(48ms)
#include <iostream>
#include <vector>
using namespace std;
#define DEBUG 0
typedef long long LL;
template<typename T>
void PrimeFactor(T n, vector<pair<T, int> >& factor) {
factor.clear();for (T i = 2; i * i <= n; ++i) {
if (n % i == 0) {
0));
factor.push_back(make_pair(i, do {
n /= i;
++factor.back().second;while (n % i == 0);
}
}
}if (n != 1)
1));
factor.push_back(make_pair(n,
}
LL n, ans;int> > ps;
vector<pair<LL, void dfs(int i, LL phi, LL now) {
if (i == ps.size()) {
ans += phi * (n / now);else {
} 1, phi, now);
dfs(i + 1);
phi *= (ps[i].first -
now *= ps[i].first;for (int j = 1; j <= ps[i].second; ++j) {
1, phi, now);
dfs(i +
phi *= ps[i].first;
now *= ps[i].first;
}
}
}int main() {
cin >> n;
PrimeFactor(n, ps);#if DEBUG
for (auto pa : ps) {
' ' << pa.second << endl;
cout << pa.first <<
}
cout << endl;#endif
0, 1, 1);
dfs(
cout << ans << endl;
return 0;
}