「BZOJ 4804」欧拉心算

Description

题目链接：BZOJ 4804

求如下式子的值：

$$\sum_{i=1}^n\sum_{j=1}^n\varphi(\gcd(i,j))$$

本题 $T$ 组数据。

数据范围：$1\le T\le 5000$，$1\le n\le 10^7$

---

Solution

我们直接拆式子：

$$\begin{aligned} \text{原式}&=\sum_{i=1}^n\sum_{j=1}^n\varphi(\gcd(i,j)) \\ &=\sum_{d=1}^n\varphi(d)\sum_{i=1}^n\sum_{j=1}^n \left[\gcd(i,j)=d\right] \\ &=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left[\gcd(i,j)=1\right]\\ &=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}2\times\varphi(i)-1 \end{aligned}$$

我们记 $sum(k)=\sum_{i=1}^k\varphi(i)$，那么有：

$$\begin{aligned} \text{原式}&=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}2\times\varphi(i)-1 \\ &=\sum_{d=1}^n\varphi(d)(2\times sum\left(\left\lfloor\frac{n}{d}\right\rfloor\right)-1) \end{aligned}$$

我们发现这里的 $\left\lfloor\frac{n}{d}\right\rfloor$ 只有 $\sqrt n$ 种取值，因此我们可以数论分块求解。

时间复杂度：$O(T\sqrt n)​$

---

Code

#include <cstdio>

const int N=1e7+5,M=1e6+5;
int n,tot,p[M],phi[N];
long long sum[N];
bool flg[N];

void sieve(int n) {
    phi[1]=1;
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            } else {
                phi[i*p[j]]=phi[i]*phi[p[j]];
            }
        }
    }
    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+phi[i];
}
int main() {
    sieve(N-5);
    int T;
    for(scanf("%d",&T);T--;) {
        int n;
        scanf("%d",&n);
        long long ans=0;
        for(int i=1,j;i<=n;i=j+1) {
            j=n/(n/i);
            ans+=(2LL*sum[n/i]-1)*(sum[j]-sum[i-1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}