题解 P1891 【疯狂 LCM】

· · 题解

ans=\sum_{i=1}^nlcm(i,n) \begin{aligned} ans & =\sum_{i=1}^nlcm(i,n) \\ & =\sum_{i=1}^n\frac{i\cdot n}{gcd(i,n)} \\ & =n\times \sum_{i=1}^n\frac{i}{gcd(i,n)} \\ & =n\times\sum_{i=1}^ni\sum_{d=1}^i\frac{[gcd(i,n)=d]}{d} \\ & =n\times \sum_{d|n}\sum_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}i\cdot[gcd(i,\frac{n}{d})=1] \end{aligned}

我们看后面的东西

设

g(n)=\sum_{i=1}^ni\cdot [gcd(i,n)=1]

我们知道更相减损术

gcd(a,b)=gcd(a,a-b)

所以

gcd(i,d)=1\Leftrightarrow gcd(d-i,d)=1

所以

对于每一个i，都有另一个d-i与其对应，而且两个数的和是个定值！

所以

g(n)=\frac{\varphi(n)}{2}\times d

但是g(1)是个特例，所以要特别处理

g出来了之后我们再预处理答案，核心代码如下

for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j += i) {
            S[j] += (g[i] * i + 1) >> 1;
        }
    }

这样就可以做到了。

#include<cstdio>
#define Starseven main
#define ll long long
namespace lyt {
    void read(int &x){
    char ch=getchar();int re=0,op=1;
    while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){re=(re<<3)+(re<<1)+ch-'0';ch=getchar();}
    x = re * op;
    return ;
    }
    void read(long long &x){
    char ch=getchar();long long re=0,op=1;
    while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){re=(re<<3ll)+(re<<1ll)+ch-'0';ch=getchar();}
    x = re * op;
    return ;
    }
    void write(int x){
        if(x<0){putchar('-');x=-x;}
        if(x>9) write(x/10);
        putchar(x%10+'0');
        return ;
    }//记得自己加空格和换行 
    void write(long long x){
        if(x<0){putchar('-');x=-x;}
        if(x>9) write(x/10);
        putchar(x%10+'0');
        return ;
    }//记得自己加空格和换行
    int max(int x,int y){return x<y?y:x;}
    int min(int x,int y){return x<y?x:y;}
    int abs(int x){return x<0?-x:x;}
    long long max(long long x,long long y){return x<y?y:x;}
    long long min(long long x,long long y){return x<y?x:y;}
    long long abs(long long x){return x<0?-x:x;}
    double abs(double x){return x<0?-x:x;}
    void swap(int &a,int &b) {a ^= b ^= a ^= b;}
    void swap(long long &a,long long &b) {a ^= b ^= a ^= b;}
}using namespace lyt;
const int N = 1e6;
int prime[N + 20], num;
ll S[N + 20], g[N + 20];
bool vis[N + 20];

void Init(void) {
    g[1] = 1;
    for (int i = 2; i <= N; i++) {
        if(!vis[i]) {
            g[i] = i - 1;
            prime[++num] = i;
        }
        for (int j = 1; j <= num && prime[j] * i <= N; j++) {
            int x = prime[j] * i;
            vis[x] = true;
            if(i % prime[j] == 0) {
                g[x] = g[i] * prime[j];
                break;
            }
            g[x] = g[i] * g[prime[j]];
        }
    }
    return ;
}

int Starseven(void) {
    int t;
    read(t);
    Init();
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j += i) {
            S[j] += (g[i] * i + 1) >> 1;//我这里没有特判1，而是用了一点小技巧
        }
    }
    while(t--) {
        int n;
        read(n);
        write(S[n] * n * 1ll);
        puts("");
    }
    return 0;   
}