「SPOJ 5971」LCMSUM

Description

题目链接：SPOJ 5971

求如下式子的值：

$$\sum_{i=1}^n \operatorname{lcm}(i,n)$$

本题 $T$ 组数据。

数据范围：$1\le T\le 3\times 10^5$，$1\le n\le 10^6$

---

Solution

易得原式即

$$\sum_{i=1}^n \frac{i\cdot n}{\gcd(i,n)}$$

根据 $\gcd(a,n)=1$ 时一定有 $\gcd(n-a,n)=1$ ，可将原式化为

$$\frac{1}{2}\cdot(\sum_{i=1}^{n-1}\frac{i\cdot n}{\gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i\cdot n}{\gcd(i,n)})+n$$

上述式子中括号内的两个 $\sum$ 对应的项相等，故又可以化为

$$\frac{1}{2}\cdot \sum_{i=1}^{n-1}\frac{n^2}{\gcd(i,n)}+n$$

可以将相同的 $\gcd(i,n)$ 合并在一起计算，故只需要统计 $\gcd(i,n)=d$ 的个数。当 $\gcd(i,n)=d$ 时，$\gcd(\frac{i}{d},\frac{n}{d})=1$，所以 $\gcd(i,n)=d$ 的个数有 $\varphi(\frac{n}{d})$ 个。

故答案为

$$\frac{1}{2}\cdot\sum_{d|n}\frac{n^2\cdot\varphi(\frac{n}{d})}{d}+n$$

变换求和顺序，设 $ d’=\frac{n}{d}$，式子化为

$$\frac{1}{2}n\cdot\sum_{d'|n}d'\cdot\varphi(d')+n$$

设 $g(n)=\sum_{d|n} d\cdot\varphi(d)$，已知 $g$ 为积性函数，于是可以 $O(n)$ 预处理。最后枚举 $d$，统计贡献即可。

时间复杂度：$O(n\log n)$

---

Code

#include <cstdio>
const int N=1000000;
int tot,p[N+5],phi[N+5];
long long ans[N+5];
bool flg[N+5];

void solve() {
    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;
            }
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
    for(int i=1;i<=N;++i) {
        for(int j=1;i*j<=N;++j) {
            ans[i*j]+=1LL*j*phi[j]/2;
        }
    }
    for(int i=1;i<=N;++i) ans[i]=1LL*i*ans[i]+i;
}
int main() {
    int T,n;
    solve();
    for(scanf("%d",&T);T;--T) {
        scanf("%d",&n);
        printf("%lld\n",ans[n]);
    }
    return 0;
}