题目链接
https://www.luogu.com.cn/problem/P3327
题解
首先,我们可以证明(详细证明后附):
$$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; }