[洛谷 3327,loj 2185][SDOI2015]约数个数和

题目链接

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

https://loj.ac/problem/2185

题解

首先，我们可以证明（详细证明后附）：

$$d(ij)=\sum_{x | i}\sum_{y | j}[\gcd(x,y)=1]$$

从而所求为：

$$\sum_{i=1}^n \sum_{j=1}^m \sum_{x | i}\sum_{y | j}[\gcd(x,y)=1]$$

这里不妨设 \(n \leq m\)。

先枚举 \(x,y\)：

$$\sum_{x=1}^n \sum_{y=1}^m \left \lfloor \frac{n}{x} \right \rfloor \left \lfloor \frac{m}{y} \right \rfloor [\gcd(x,y)=1]$$

这时候套路性地换掉 \([\gcd(x,y)=1]\)：

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

改为枚举 \(d\)：

$$\sum_{d=1}^n \mu(d) \sum_{x=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{y=1}^{\left \lfloor \frac{m}{d} \right \rfloor} \left \lfloor \frac{n}{dx} \right \rfloor \left \lfloor \frac{m}{dy} \right \rfloor$$

进一步推导可知：

$$\sum_{d=1}^n \mu(d) \sum_{x=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \left \lfloor \frac{n}{dx} \right \rfloor \sum_{y=1}^{\left \lfloor \frac{m}{d} \right \rfloor} \left \lfloor \frac{m}{dy} \right \rfloor$$

应用整除分块即可。这样单组测试数据即可做到 \(O(\sqrt n)\)。

公式证明

现在我们考虑证明题解开头提到的那个公式。

即，

$$d(ij)=\sum_{x | i}\sum_{y | j}[\gcd(x,y)=1]$$

我们对 \(i,j\) 分别进行质因数分解。

现在我们需要从 \(ij\) 中选出 \(p^k\)，其中 \(i\) 中有因子 \(p^a\)，\(j\) 中有因子 \(p^b\)，我们规定：

• 若 \(k \leq a\)，直接从 \(i\) 中选。
• 否则，我们直接从 \(j\) 中取得 \(p^{k-a}\)。

现在我们需要挑出一个数 \(n=\prod_{i=1}^d p_i^{c_i}\)，根据上面的规则，每个 \(n\)，都与一种挑选方案一一对应。

又因为一个因子只能在一个数中取，从而 \(x,y\) 互质，定理得证。

// Problem: #2185. 「SDOI2015」约数个数和
// Contest: LibreOJ
// URL: https://loj.ac/problem/2185
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <iostream>
#include <algorithm>
#define N 50000
using namespace std;
long long mu[50005],pri[50005],vis[50005],s[50005];
void init()
{
 int cnt=0;
 mu[1]=vis[1]=1;
 for(int i=2;i<=N;i++)
 {
  if(!vis[i])
  {
   mu[i]=-1;
   pri[++cnt]=i;
  }
  for(int j=1;j<=cnt&&i*pri[j]<=N;j++)
  {
   vis[i*pri[j]]=1;
   if(i%pri[j]==0)
   {
    mu[i*pri[j]]=0;
    break;
   }
   mu[i*pri[j]]=-mu[i];
  }
 }
 for(int i=1;i<=N;i++)
  mu[i]+=mu[i-1];
 for(int i=1;i<=N;i++)
 {
  long long res=0;
  for(int l=1,r;l<=i;l=r+1)
  {
   r=i/(i/l);
   res+=1ll*(r-l+1)*(i/l);
  }
  s[i]=res;
 }
}
int main()
{
 int t;
 cin>>t;
 init();
 while(t--)
 {
  int x,y;
  cin>>x>>y;
  if(x>y)swap(x,y);
  long long ans=0;
  for(int l=1,r;l<=x;l=r+1)
  {
   r=min(x/(x/l),y/(y/l));
   ans+=1ll*(mu[r]-mu[l-1])*s[x/l]*s[y/l];
  }
  cout<<ans<<endl;
 }
 return 0;
}