欧拉函数的应用:利用欧拉函数快速求解 1~n 中两两数字的最小公倍数(LightOJ 1375 LCM Extreme)

今天遇到一个十分 Dark 的题目,让你求:

\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} lcm(i,j)

一共 T 组数据,数据范围是:T \leqslant 2 \ast 10^5, n \leqslant 3\ast 10^6……
题目链接:LightOJ 1375 LCM Extreme

这题据说可以用莫比乌斯反演做,但是看了一大堆似乎还是没怎么懂……但是翻大佬的博客找到一个精妙的做法~

首先把上面那个公式分开,先求:

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

显然有:

lcm(n,i)=\frac {ni} {gcd(n,i)}

g=gcd(n,i),则 \displaystyle \frac n g\displaystyle \frac i g 互质。
接下来要用到一个公式:小于 x 的与 x 互质的数之和为 \displaystyle \frac {x \ast \varphi(x)} {2}
所以小于 \displaystyle \frac n g 的且与其互质之数之和:

\frac {(\frac n g)\ast \varphi(\frac n g)} {2}

\displaystyle d=\frac n g,则 dn 的因子。方便后面枚举。得到:

\sum_{i=1}^{n-1} \frac i g=\frac {d \ast \varphi (d)} {2}

因为我们要让左边得到 lcm(n,i),根据 \displaystyle lcm(n,i)=\frac {n\ast i} {gcd(n,i)},我们可以将左边的 \displaystyle \frac i g 乘上 n提取出来得到:

\sum_{i=1}^{n-1} lcm(n,i)=n \ast \frac {d \ast \varphi (d)} {2}

哇!!!就要成功了!接下来考虑 i=n 的情况,因为 i=n 的时候 \displaystyle \frac n g=1,需要特判:

\sum_{i=1}^{n} lcm(n,i)=n+ n \ast \frac {d \ast \varphi(d)} 2

最后我们只需要用欧拉筛进行一次 O(N) 求欧拉函数就可以方便地求出 \displaystyle \sum_{i=1}^{n} lcm(n,i) 了~

现在回到原问题,求出 \displaystyle \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} lcm(i,j),只要前缀和累加一下就好了!!

还有说下这题题目让我们对 2^{32} 取模,如果直接开 long long 再模可能会爆内存。处理技巧是直接开 unsigned int,然后自然溢出(也就是不用模的)。最后输出不能用 %d,要用 %u

贴上代码(要注意一点细节,不然还是可能爆内存……):

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=3000005,N=3000000;
int T,n,prime[maxn];
bool vis[maxn];
unsigned long long f[maxn];
unsigned int phi[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return  ret*f;
}
inline void BuildPhi(){ // 线性筛法求欧拉函数,黑科技!
    phi[1]=1;
    memset(vis,1,sizeof(vis));
    vis[1]=false;
    for (int i=2;i<=N;i++){
        if (vis[i]){
            phi[i]=i-1;
            prime[++prime[0]]=i;
        }
        for (int j=1;j<=prime[0];j++){
            if (i*prime[j]>N) break;
            vis[i*prime[j]]=false;
            if (i%prime[j]) phi[i*prime[j]]=(prime[j]-1)*phi[i];
            else {phi[i*prime[j]]=prime[j]*phi[i];break;}
        }
    }
}
inline void BuildSum(){
    for (int i=1;i<=N;i++){
        for (int j=i;j<=N;j+=i) f[j]+=(unsigned long long)phi[i]*i/2*j; // i 作为因子
        f[i]=f[i-1]+f[i]; // i 之前的一定都求好了,干脆累加起来
    }
}
int main(){
    T=read();
    BuildPhi();
    BuildSum();
    for (int t=1;t<=T;t++){
        n=read();
        printf("Case %d: %llu\n",t,f[n]);
    }
    return 0;
}
本文采用 BY-NC-SA 4.0 协议,欢迎转载。如有错误欢迎指出。
本文链接: https://skywt.cn/posts/eular-function-use/

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。