题解 SP5971 【LCMSUM - LCM Sum】

derta · 2020-05-08 12:34:46 · 题解

SP5971 LCMSUM - LCM Sum

题意

$$\sum_{i=1}^{n} \operatorname{lcm}(i,n)$$ 其中 $1 \leqslant T \leqslant 3\times10^5$，$n \leqslant 10^6

思路

来一发不需要 \varphi 函数的做法

根据 \operatorname{lcm}(x,y)=\dfrac{xy}{\gcd(x,y)}，得

\sum_{i=1}^{n}\dfrac{ni}{\gcd(n,i)}

把 n 拎到前面罚站

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

枚举 \gcd(n,i) 的值

n\sum_{k|n}\sum_{k|i}^{n}[\gcd(n,i)=k]\frac{i}{k}

将 i 与 n 除以 k

n\sum_{k|n}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}[\gcd(\frac{n}{k},i)=1]i

由 \sum_{d|n}\mu(d)=[n=1]，得

n\sum_{k|n}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}i\sum_{d|\gcd(\frac{n}{k},i)}\mu(d)

显然

n\sum_{k|n}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}i\sum_{d|\frac{n}{k},d|i}\mu(d)

改变顺序，先枚举 d

n\sum_{k|n}\sum_{d|\frac{n}{k}} \mu(d)\sum_{d|i}^{\lfloor\frac{n}{k}\rfloor}i

易知

n\sum_{k|n}\sum_{d|\frac{n}{k}} \mu(d)d\sum_{d|i}^{\lfloor\frac{n}{kd}\rfloor}i

令 S(n)=\sum_{i=1}^{n}i=\dfrac{n(n+1)}{2}，则

n\sum_{k|n}\sum_{d|\frac{n}{k}} S(\lfloor\frac{n}{kd}\rfloor)\mu(d)d

令 M=kd

n\sum_{k|n}\sum_{d|\frac{n}{k}} S(\lfloor\frac{n}{M}\rfloor)\mu(d)d

枚举 M

n\sum_{M|n}S(\lfloor\frac{n}{M}\rfloor)\sum_{d|M}\mu(d)d

令 f(n)=\sum_{d|n}\mu(d)d，考虑如何线性筛出 f(n)

（提示：下面的几个情况和欧拉筛一样）

n=1$，$f(n)=\mu(1)\times 1=1
n \in \mathbb{P}$，则 $f(n)=\mu(1)\times1+\mu(n)\times n=1-n
否则，设 n=ij，其中 j 为 n 的最小质因子
- 若 i \operatorname{mod}j=0，则 f(ij)=f(i)，因为有 j 之后，产生的所有新的质因子 d，都有 \mu(d)=0
- 否则，f(ij)=f(i)f(j)，因为 i 的每一个质因子 t 乘 j 之后都有 \mu(tj)=-\mu(d)，所以 f(ij)=f(i)-jf(i)=(1-j)f(i)=f(i)f(j)

这时候我们已经能做到 O(n+T\sqrt n) 了，但计算一下，3\times 10^5 \times\sqrt{10^6}=3\times 10^8，时限还是 527\operatorname{ms}，不足以通过本题。那么我们可以用类似埃氏筛的方法，筛出 ans_n=\sum_{M|n}S(\lfloor\dfrac{n}{M}\rfloor)f(M)，最后输出 n\times ans_n，可以达到 O(n\log_2 n+T) 的时间复杂度，具体见代码

#include <iostream>
const int MAXN = 1000000, lnMAXN = 12;
int Prime[MAXN/lnMAXN + 5], size; //Prime[i]为第i个质数 
long long f[MAXN + 5], ans[MAXN + 5]; //开long long 
bool not_prime[MAXN + 5]; //not_prime[i]=true 表示i为合数，否则为质数 

inline long long S(int n)
{ return 1LL*n*(n + 1) >> 1; } //高斯求和公式，别忘了long long 

void sieve(int n) {
    f[1] = 1; 
    not_prime[1] = true;
    //筛f 
    for(int i = 1; i <= n; ++i) {
        if(not_prime[i] == false) { //i为质数 
            f[i] = 1 - i; //第1种情况 
            Prime[size++] = i; //加入质数表 
        }
        for(int j = 0; j < size && i*Prime[j] <= n; ++j) {
            not_prime[i*Prime[j]] = true;
            if(i%Prime[j] == 0) {
                f[i*Prime[j]] = f[i]; //第2种情况 
                break;
            }
            f[i*Prime[j]] = f[i]*f[Prime[j]]; //第3种情况 
        }
    }
    //筛ans 
    for(int i = 1; i <= n; ++i)
        for(int j = 1; i*j <= n; ++j)
            ans[i*j] += S(i)*f[j];
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);
    sieve(MAXN);
    int t, n;
    std::cin >> t;
    while(t--) {
        std::cin >> n;
        std::cout << 1LL*n*ans[n] << "\n";
    }
    return 0;
}

最后，对筛 ans 的复杂度上界进行证明。

这个过程的时间复杂度事实上为

\sum_{i=1}^{n}\dfrac{n}{i}

那么我们将 \dfrac{n}{2^i},\dfrac{n}{2^i+1},\dfrac{n}{2^i+2},\cdots,\dfrac{n}{2^{i+1}-1} 这 2^i 个数全部看做 \dfrac{n}{2^i}，所以原式上界为 n\log_2 n