[洛谷 1447][NOI2010]能量采集

题目链接

https://www.luogu.com.cn/problem/P1447

题解

为了方便起见，不妨设 $n \leq m$。

容易发现我们要求的是：

$$ans=\sum_{i=1}^n \sum_{j=1}^m (2 \times \gcd(i,j)-1)$$

我们先提出公因式：

$$ans=2 \sum_{i=1}^n \sum_{j=1}^m \gcd(i,j) – n \times m$$

到这里我们有两种做法。

做法一

（这个做法和 [POI2007]ZAP-Queries 一致）

套路性地枚举 $\gcd$ 的值：

$$ans=2\sum_{d=1}^{n} d\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d] -n \times m$$

我们设：

$$f(d)=\sum_{i=1}^{n} \sum_{j=1}^{m}[\gcd(i,j)=d]$$

要求的答案就变成了：

$$ans=2\sum_{d=1}^{n}d \times f(d) – n \times m$$

将 $f(d)$ 套路性的除一个 $d$：

$$f(d)=\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}[\gcd(i,j)=1]$$

利用莫比乌斯函数的性质：$\sum_{d|n}\mu(d)=[x=1]$ 将 $[\gcd(i,j)=1]$ 换掉：

$$f(d)=\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor} \sum_{x|\gcd(i,j)}\mu(x)$$

有这样一个性质：若 $x|\gcd(i,j)$，则 $x|i$ 且 $x|j$。所以我们把这个条件拆开：

$$f(d)=\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor} \sum_{x|i,x|j}\mu(x)$$

接下来枚举 $x$：

$$f(d)=\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor} \sum_{x=1}^{a}\mu(x)[x|i][x|j]$$

交换求和顺序：

$$f(d)=\sum_{x=1}^n \mu(x) \sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} [x|i] \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}[x|j]$$

从而得到：

$$f(d)=\sum_{k=1}^{n}\mu(k)\left \lfloor \frac{n}{kd} \right \rfloor\left \lfloor \frac{m}{kd} \right \rfloor$$

将 $f(d)$ 代入 $ans$ 中：

$$ans=2\sum_{i=1}^n d \sum_{k=1}^{n}\mu(k)\left \lfloor \frac{n}{kd} \right \rfloor\left \lfloor \frac{m}{kd} \right \rfloor – n \times m$$

对于每个 $d$，我们都需要整除分块一次，时间复杂度 $O(n \ln n)$。

做法二

还能再快一点吗？

欧拉函数有这样一个性质：$\sum_{d|n}\varphi(d)=n$。

于是我们把刚开始的 $\gcd(i,j)$ 换掉：

$$ans=2 \sum_{i=1}^n \sum_{j=1}^m \sum_{d|\gcd(i,j)}\varphi(d) – n \times m$$

把内层的条件拆开：

$$ans=2 \sum_{i=1}^n \sum_{j=1}^m \sum_{d|i,d|j}\varphi(d) – n \times m$$

交换求和顺序：

$$ans=2\sum_{d=1}^n \varphi(d) \sum_{i=1}^n [d|i] \sum_{j=1}^m [d|j] – n \times m$$

从而得到：

$$ans=2\sum_{d=1}^n \varphi(d)\left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor – n \times m$$

只需一次 $O(n)$ 的线性筛和一次 $O(\sqrt n)$ 的整除分块就解决本题了。

（多组询问的时候就吊打做法一了）

#include <iostream>
#include <algorithm>
#define N 100000
using namespace std;
long long pri[100005],phi[100005];
void init()
{
 phi[1]=1;
 int cnt=0;
 for(int i=2;i<=N;i++)
 {
  if(!phi[i])
  {
   phi[i]=i-1;
   pri[++cnt]=i;
  }
  for(long long j=1;j<=cnt&&i*pri[j]<=N;j++)
  {
   if(i%pri[j]==0)
   {
    phi[i*pri[j]]=phi[i]*pri[j];
    break;
   }
   phi[i*pri[j]]=phi[i]*phi[pri[j]];
  }
 }
 for(int i=1;i<=N;i++)
  phi[i]+=phi[i-1];
}
int main()
{
 long long n,m;
 cin>>n>>m;
 init();
 long long ans=0;
 if(n>m)swap(n,m);
 for(int l=1,r;l<=n;l=r+1)
 {
  r=min(n/(n/l),m/(m/l));
  ans+=(phi[r]-phi[l-1])*(n/l)*(m/l);
 }
 ans=ans*2-n*m;
 cout<<ans<<endl;
 return 0;
}