3944: Sum

3944: Sum

Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2415  Solved: 666 [ Submit][ Status][ Discuss]

Description

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

HINT

Source

[ Submit][ Status][ Discuss] 简单的说就是求欧拉函数和莫比乌斯函数的前缀和 就留一个杜教筛的笔记吧，，，

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #include<bitset> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 5E6 + 555; typedef long long LL; int T,tot,pri[maxn],mu[maxn]; LL phi[maxn]; bool not_pri[maxn]; map <int,pair<LL,LL> > M; void Solve(int n,LL &Ans1,LL &Ans2) { if (n < maxn) { Ans1 = phi[n]; Ans2 = mu[n]; return; } if (M.count(n)) {Ans1 = M[n].first; Ans2 = M[n].second; return;} Ans1 = 1LL * n * (n + 1LL) / 2LL; Ans2 = 1LL; for (int i = 2,last; ; ++i) { last = n / (n / i); LL ret1,ret2; Solve(n / i,ret1,ret2); Ans1 -= ret1 * (last - i + 1); Ans2 -= ret2 * (last - i + 1); i = last; if (i == n) break; } M[n] = make_pair(Ans1,Ans2); } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif mu[1] = phi[1] = 1; for (int i = 2; i < maxn; i++) { if (!not_pri[i]) { pri[++tot] = i; mu[i] = -1; phi[i] = i - 1; } for (int j = 1; j <= tot; j++) { LL Nex = 1LL * i * pri[j]; if (Nex >= maxn) break; not_pri[Nex] = 1; if (i % pri[j] == 0) { phi[Nex] = phi[i] * pri[j]; mu[Nex] = 0; break; } mu[Nex] = -mu[i]; phi[Nex] = phi[i] * (pri[j] - 1); } phi[i] += phi[i - 1]; mu[i] += mu[i - 1]; } cin >> T; while (T--) { int n; scanf("%d",&n); if (!n) {puts("0 0"); continue;} LL Ans1,Ans2; Ans1 = Ans2 = 0; Solve(n,Ans1,Ans2); printf("%lld %lld\n",Ans1,Ans2); } return 0; }