化神奇为腐朽的数论—— 能量采集 总结

什么时候我这种蒟蒻也开始看$\text{NOI}$的题了呢？（逃 好吧，也是[$\text{hkr04}$](https://www.luogu.org/space/show?uid=111528)这位神犇介绍我看的，而看到这道题之前[$\text{HKZeril}$](https://www.luogu.org/space/show?uid=66073)神犇把与这题有关的一个结论介绍给了我。在此向这两位神犇表示深深的谢意！ 好的，言归正传。我们先看一个结论（定理）。~~这次不会是什么恋爱循环定理啦~~ 定理 $2.33$ 设$A(0,0),B(n,m)(n,m\in \mathbb{N}_{+})$，那么线段$AB$上整点的个数即为$\gcd(n,m)+1$。 如何证明这个定理呢？ 设点$C(x,y)(x,y\in \mathbb{N})$在线段$AB$上，那么有$\frac{x}{n}=\frac{y}{m}$。 设$g=\gcd(n,m),n'=\frac{n}{g},m'=\frac{m}{g}$。则上式可化为$\frac{x}{n'}=\frac{y}{m'}$，则$xm'=yn'$。 由$n'\perp m'$，得$n'\mid x,m'\mid y$。现在可设$k=\frac{x}{n'}=\frac{y}{m'}(k\in \mathbb{N})$，又由线段的条件知$0\le k \le g$。 我们构造一个点集$S=\{(kn',km')\mid k\in \mathbb{N}, 0\le k\le g\}$，可以发现点集中的点全部都在线段$AB$上。又根据上面的讨论知道线段$AB$上的整点必须满足集合$S$的条件，因此我们就可以下定论：$S$是线段$AB$上的所有整点的集合。易知$\left| S \right|=g+1$。定理证毕。 现在请看题（逃 [P1447 [NOI2010]能量采集](https://www.luogu.org/problemnew/show/P1447) 读题并结合定理，这道题要求的就是$$2\sum^{n}_{i=1}\sum^{m}_{j=1}(\gcd(i,j))-nm$$ （注意这题的线段$AB$不含端点，因此每一条线段上的整点数应为$\gcd(i,j)-1$。） 上式的难点就在于$\sum^{n}_{i=1}\sum^{m}_{j=1}\gcd(i,j)$。下面请看一些神奇的推导！ 首先，我们再看一个定理： 定理$2.333$ $\text{ }\varphi$函数对约数求和定理 （《数论入门》$\text{P35}$） $$\forall n\in \mathbb{N_{+}},\sum_{d\mid n}\varphi(d)=n$$ 证明：根据$\varphi$函数的定义，$\varphi(n)$表示$[1,n]$中与$n$互质的整数的数目。 设$d\mid n,n=kd(k\in\mathbb{N})$，设集合$S=\{x\in\mathbb{N_{+}}\mid x\perp d\}$，则$\left| S\right|=\varphi (d)$。设函数$f:S\rightarrow \mathbb{N}$，$f(x)=kx$。设$f(x)$的值域为$S'$。由于$f$是单射，因此$\left|S'\right|=\left|S\right|=\varphi(d)$。 对于$S'$中的每一个元素$f(x)=kx$，由于$x\perp d$，因此$\gcd(f(x),n)=\gcd(kx,kd)=k\gcd(x,d)=k$。 因此，我们可以说，$S'=\{x\in\mathbb{N_{+}}\mid \gcd(x,n)=k\}$。 $\{k\}$和$\{d\}$中的元素是一一对应的，且不同$k$的$S'$两两不交，因此$\bigcup S'$即为$[1,n]\cap\mathbb{N}$，定理证毕。 根据这个定理，我们可以对$\sum^{n}_{i=1}\sum^{m}_{j=1}\gcd(i,j)$这个式子做一些似乎无意义的变形：$$\sum^{n}_{i=1}\sum^{m}_{j=1}\gcd(i,j)=\sum^{n}_{i=1}\sum^{m}_{j=1}\sum_{d\mid \gcd(i,j)}\varphi (d)=\sum^{n}_{i=1}\sum^{m}_{j=1}\sum_{d\mid i,d\mid j}\varphi (d)$$ 然而，这一步变形却是$\text{AC}$的开始。接下来我们考虑更换枚举顺序（即交换求和号的顺序）。 考虑对于每一个数$d$，$\varphi(d)$会被加几次呢？也就是说，在$1\le i\le n,1\le j\le m$的范围内，有多少对$(n,m)$满足$d\mid i,d\mid j$呢？ 在范围内，$i$有$\lfloor \frac{n}{d} \rfloor$种选法，$j$有$\lfloor \frac{m}{d} \rfloor$种选法，根据乘法原理，满足条件的数对就有$\lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor$个。于是$\varphi(d)$对答案的贡献便是$\lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor \varphi(d)$。 写到这里，答案已经呼之欲出了，便是 $$\sum^{\min(n,m)}_{i=1}\lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor \varphi(d)$$ 接下来的事情便十分简单，使用欧拉筛（线性筛）计算出$\varphi$函数的值，再直接求和即可。时间复杂度$\text{O}(n)$。 当然，推导到这一步需要很强的思维能力。为了简化思维难度，大佬们研发出了莫比乌斯~~繁衍~~反演、狄利克雷卷积等工具。这题当然也可以用这些方法推导式子。 最后上代码。 ```cpp #include <iostream> #include <algorithm> #define MAXN 100005 using namespace std; void eular(int n); //线性筛求欧拉函数 int phi[MAXN]; //用来保存欧拉函数的值 int minp[MAXN],prime[MAXN],pr; //质数表，线性筛用 int main(void){ int n,m; long long ans=0; cin >> n >> m; if (n>m) swap(n,m); //n=min(n,m) eular(n); for (int i=1;i<=n;i++) ans+=((long long)(n)/i)*((long long)(m)/i)*phi[i]; ans*=2; //2倍gcd之和 ans-=(long long)(n)*m; //再减去mn cout << ans << endl; return 0; } void eular(int n){ phi[1]=1; int t; for (int i=2;i<=n;i++){ if (!minp[i]){ minp[i]=i; phi[i]=i-1; //phi(p)=p-1,其中p是质数 prime[pr++]=i; } for (int j=0;j<pr && (t=i*prime[j])<=n;j++){ minp[t]=prime[j]; //minp表示最小质因子 if (prime[j]==minp[i]){ phi[t]=prime[j]*phi[i]; break; } //else phi[t]=(prime[j]-1)*phi[i]; } } } ```