SPOJ - LCMSUM / 线性筛/ 积性函数

· · 个人记录

题意简单粗暴，要我们求

\sum_{i=1}^{n}Lcm(i,n)

按 Lcm 定义展开

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

有 gcd(i,n)=1时 gcd(n-i,n)=1 因此

\frac{1}{2} \big( \sum_{i=1}^{n-1}\frac{i*n}{gcd(i,n)} + \sum_{i=n-1}^{1}\frac{i*n}{gcd(i,n)}\big) +n =\frac{1}{2} \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 的个数有 \phi(\frac{n}{d}) 个。

故答案为

\frac{1}{2} \sum_{d|n}\frac{n^2}{d}\phi(\frac{n}{d})+\frac{n}{2} =\frac{n}{2} \sum_{d|n}d'\phi(d')+\frac{n}{2}

积性函数可以线性筛，复杂度 O(n+T)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
int Gcd(int a,int b){if (b == 0) return a; return Gcd(b , a%b);}
int Lcm(int a, int b){ return a/Gcd(a,b)*b;}
template <class T>
void read(T &x) {
    static char ch;
    static bool neg;
    for(ch = neg = 0; ch < '0' || '9' < ch; neg |= ch == '-', ch = getchar());
    for(x = 0; '0' <= ch && ch <= '9'; (x *= 10) += ch - '0', ch = getchar());
    x = neg ? -x : x;
}
const int maxn = 1e6 + 10;
int vis[maxn],prm[maxn],tot;
int phi[maxn];
LL ans[maxn];
void getphi(){
    vis[1] = 1;
    phi[1] = 1;
    for(int i=2; i<maxn; i++){
        if (!vis[i]){
            prm[++tot] = i;
            phi[i] = i-1;
        }
        for(int j=1; j<=tot && i * prm[j] < maxn; j++){
            vis[i*prm[j]] = 1;
            if (i % prm[j] == 0){
                phi[i*prm[j]] = phi[i] * prm[j];
                break;
            }
            phi[i * prm[j]] = phi[i] * (prm[j] - 1);
        }
    }
    for(int i=1; i<maxn; i++){
        for(int j=1; i*j<maxn; j++){
            ans[i*j] += 1ll * j * phi[j];
        }
    }
    for(int i=1; i<maxn; i++){
        ans[i] = ans[i] * i + i; 
    }
}
int main(){
    getphi();
    int T;
    read(T);
    while(T--){
        int n;
        read(n);
        printf("%lld\n",ans[n]/2);
    }
    return 0;
}