BZOJ4804: 欧拉心算

Description

给出一个数字N

Input

第一行为一个正整数T，表示数据组数。

接下来T行为询问，每行包含一个正整数N。

T<=5000,N<=10^7

Output

按读入顺序输出答案。

Sample Input

1
10

Sample Output

136

Solution

莫比乌斯反演。
还有一种用欧拉函数的神仙做法

\[ \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^n\phi((i,j))\&=\sum_{d=1}^{n}\phi(d)\sum_{i=1}^{n}\sum_{j=1}^n[(i,j)=d]\&=\sum_{d=1}^{n}\phi(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{k|(i,j)}\mu(k)\&=\sum_{d=1}^{n}\phi(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{kd}\rfloor^2\mu(k) \end{aligned} \]

这样可以做到单次询问\(O(n)\)，可以继续推下去
\[ \begin{aligned} &设T=kd\&\sum_{d=1}^{n}\phi(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{kd}\rfloor^2\mu(k)\&=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor^2\sum_{k|T}\mu(k)\phi(\frac{T}{k})\\end{aligned} \]
发现后面那个玩意是个狄利克雷卷积形式，所以这玩意是个积性函数，上线性筛

当\(T\)为质数时
\[ \begin{aligned} &\sum_{k|T}\mu(k)\phi(\frac{T}{k})\&=\mu(1)*\phi(T)+\mu(T)*\phi(1)\&=T-1-1\&=T-2 \end{aligned} \]
当\(T\)为质数的平方时
\[ \begin{aligned} &\sum_{k|T}\mu(k)\phi(\frac{T}{k})\&=\phi(p)*\mu(p)+\phi(p^2)*\mu(1)\&=-(p-1)+p(p-1)\&=-p+1+p^2-p\&=p^2-2p+1\&=(p-1)^2 \end{aligned} \]
当\(T\)为质数的\(c\)次方时（\(c>2\)）
\[ \begin{aligned} &设c=3\&\sum_{k|T}\mu(k)\phi(\frac{T}{k})\&=\phi(p^3)*\mu(1)-\phi(p^2)*\mu(p)+0\&=p^3-p^2-p^2+p\&=p^3-2p^2+p\&=p(p^2-2p+1)\&=p(p-1)^2 \end{aligned} \]
同理可得当\(T=p^c（c>2）\)时，该函数的值为\(p^{c-2}(p-1)^2\)

但是有这个\(p=2\)有点麻烦，所以我们不妨直接分类讨论这两种情况

考虑在线性筛中遇到这种情况怎么搞

设以上讨论的那个函数为\(f\)

1.当i不为prime[j]倍数

根据积性函数的定义即可
\[ f(i*prime[j])=f(i)*f(prime[j]) \]

2.当\(i\)为\(prime[j]\)倍数

当\(i\)中\(prime[j]\)的指数为\(1\)时，对应上方的\(T=p^2\)的情况

（注：因为指数为\(1\)，所以\(i/prime[j]\)与\(prime[j]\)互质）
\[ \begin{aligned} &f(i*prime[j])\&=f(i/prime[j])*f(prime[j]^2)\&=f(i/prime[j])*(prime[j]-1)^2 \end{aligned} \]
当\(i\)中\(prime[j]\)的质数大于\(1\)时，对应上方\(T=p^c(c>2)\)，将结论代入即可
\[ \begin{aligned} &f(i*prime[j])\&=f(i)*prime[j]\\end{aligned} \]
（注：因为\(f(i)\)其实就是\(T=p^{c-1}\)的情况，所以直接按照上方的结论乘上p即可）

然后就做完了

复杂度\(O(n+T\sqrt{n})\)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e7 + 10;
ll p[N];
ll n, cnt;
ll F[N], sum[N];
bool vis[N];

inline void init() {
    F[1] = 1;
    for(int i = 2; i < N; ++i) {
        if(!vis[i]) p[++cnt] = i, F[i] = i - 2;
        for(int j = 1; j <= cnt && i * p[j] < N; ++j) {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) {
                if((i / p[j]) % p[j]) F[i * p[j]] = F[i / p[j]] * (p[j] - 1) * (p[j] - 1); //有平方质因子 
                else F[i * p[j]] = F[i] * p[j]; //有平方以上的质因子 
                break;
            }
            F[i * p[j]] = F[i] * F[p[j]];
        }
    }
    for(int i = 1; i < N; ++i) F[i] += F[i - 1];
}

inline ll calc(ll n) {
    ll ans = 0;
    for(ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans += (n / l) * (n / l) * (F[r] - F[l - 1]);
    }
    return ans;
}

int main() {
    int T; scanf("%d", &T); init();
    while(T--) {
        scanf("%lld", &n);
        printf("%lld\n", calc(n));
    }
}

BZOJ4804: 欧拉心算

原文：https://www.cnblogs.com/henry-1202/p/10339603.html