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