Description
给你一个正整数N,N<2^31, 求\(\sum_{i=1}^n \phi (i)\)和\(\sum_{i=1}^n \mu (i)\)
Input
一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个正整数N,代表一组询问
Output
一共T行,每行两个用空格分隔的数ans1,ans2
Sample Input
6 1 2 8 13 30 2333
Sample Output
1 1 2 0 22 -2 58 -3 278 -3 1655470 2
Solution
令F(n)为f(n)的前缀和,G(n)为g(n)的前缀和,且满足\(g(n)=\sum_{i|n}f(i)\),则有:
\begin{align}
G(n)&=\sum_{i=1}^ng(i) \
&=\sum_{j=1}^n\sum_{j|i}f(j)\
&=\sum_{j=1}^n\lfloor\frac n j \rfloor f(j) \
&=\sum_{j=1}^nF(\lfloor\frac n j \rfloor) \
\end{align}
$$ \therefore F(n)=G(n)-\sum_{i=2}^nF(\lfloor\frac n i \rfloor) $$
若G(n)可以在O(1)时间内算出,则F(n)可以在O(n^(3/4))的时间内算出(别问我复杂度是咋算的)
如果预处理前O(n^(2/3)) 的部分,则F(n)可以在O(n^(2/3))的时间内算出
然后疯狂TLE。。。抄了POPOQQQ的实现。
Code
#include <map> #include <set> #include <queue> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int INF = 1000000007; const int maxn = 5000010; map<int, LL> M, S; map<int, LL>::iterator it; int cnt; bool vis[maxn]; LL p[350003], phi[maxn], mu[maxn]; LL F(int n) { if (n <= 5000000) return phi[n]; if ((it = M.find(n)) != M.end()) return it->second; LL ret = LL(n)*LL(n+1ll)/2ll; for (LL i = 2ll, k; i <= n; i = k + 1ll) { k = n / (n / i); ret -= (k-i+1ll) * F(n/i); } return M[n] = ret; } LL G(int n) { if (n <= 5000000) return mu[n]; if ((it = S.find(n)) != S.end()) return it->second; LL ret = 1ll; for (LL i = 2ll, k; i <= n; i = k + 1ll) { k = n / (n / i); ret -= (k-i+1ll) * G(n/i); } return S[n] = ret; } inline void precal() { phi[1] = mu[1] = 1ll; for (LL i = 2; i <= 5000000; ++i) { if (!vis[i]) {p[cnt++] = i;phi[i] = i-1ll;mu[i] = -1ll;} for (int j = 0; j < cnt && i*p[j] <= 5000000ll; ++j) { vis[i*p[j]] = true; if (i%p[j] == 0ll) { phi[i*p[j]] = p[j] * phi[i]; mu[i*p[j]] = 0ll; break; } else { phi[i*p[j]] = (p[j]-1ll)*phi[i]; mu[i*p[j]] = -1ll*mu[i]; } } } for (int i = 1; i <= 5000000; ++i) { phi[i] += phi[i-1]; mu[i] += mu[i-1]; } } int main() { int n, T; precal(); scanf("%d", &T); while (T--) { scanf("%d", &n); printf("%lld %lld\n", F(n), G(n)); } }