题目描述

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;
}

原文地址：http://www.cnblogs.com/xiaocaibiancheng/p/16851957.html