[洛谷 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;
}

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据