题目描述
https://www.luogu.com.cn/problem/P1447
栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。
栋栋的植物种得非常整齐，一共有 \(n\) 列，每列有 \(m\) 棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标 \((x, y)\) 来表示，其中 \(x\) 的范围是 \(1\) 至 \(n\)，\(y\) 的范围是 \(1\) 至 \(m\)，表示是在第 \(x\) 列的第 \(y\) 棵。
由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是 \((0, 0)\)。
能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有 \(k\) 棵植物，则能量的损失为 \(2k + 1\)。例如，当能量汇集机器收集坐标为 \((2, 4)\) 的植物时，由于连接线段上存在一棵植物 \((1, 2)\)，会产生 \(3\) 的能量损失。注意，如果一棵植物与能量汇集机器连接的线段上没有植物，则能量损失为 \(1\)。现在要计算总的能量损失。
题意
就是求：
\(2\times\sum_{i=1}^n\sum_{j=1}^m(\gcd(i,j)-1)\)
\(=2\times\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)-n\times m\)
也就是求：
\(\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\)
解题思路
接下来通过狄利克雷卷积对式子进行化简：
\(\because I~*~\varphi =id\)
\(\therefore \sum_{d\mid x}I(\frac{x}{d})\varphi(d)=id(x)\)
\(\therefore \sum_{d\mid x}\varphi(d)=x\)
\(\therefore \sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\)
\(=\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid \gcd(i,j)}\varphi(d)\)
\(=\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i,d \mid j}\varphi(d)\)
接下来统计 \(\varphi(d)\) 的个数：
\(=\sum_{d=1}^{\min(n,m)}\varphi(d) (\sum_{i=1}^n[d\mid i]\times \sum_{j=1}^m[d \mid j])\)
\(=\sum_{d=1}^{\min(n,m)} \left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor \varphi(d)\)
时间复杂度 \(O(\min(n,m))\)
代码
先线性筛一下欧拉函数，再套公式。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,m,ip[N],p[N];
ll phi[N],ans;
void getphi(){
int cnt=0;
phi[1]=1;
for(int i=2;i<N;i++) ip[i]=1;
for(int i=2;i<N;i++){
if(ip[i]){
p[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*p[j]<N;j++){
ip[i*p[j]]=0;
if(i%p[j]) phi[i*p[j]]=phi[i]*phi[p[j]];
else {
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
getphi();
for(int i=1;i<=min(n,m);i++){
ans+=phi[i]*(n/i)*(m/i);
}
printf("%lld",2*ans-1ll*n*m);
return 0;
}