Description
\[\sum \limits_{i = 1}^A \sum \limits_{j = 1}^B [ \gcd(i, j) = d]
\]
\]
要\(O(\sqrt n)\)的算法
Solution
题目要求的是
\[\sum \limits_{i = 1}^A \sum \limits_{j = 1}^B [ \gcd(i, j) = d]
\]
\]
要\(O(\sqrt n)\)的算法
对式子进行套路性的变形
\[\sum \limits_{i = 1}^{ \lfloor \frac{A}{d} \rfloor} \sum \limits_{j = 1}^{ \lfloor \frac{B}{d} \rfloor} [ \gcd(i, j) = 1]
\]
\]
(代入 \(\epsilon = 1 \ast \mu\))
\[\sum \limits_{i = 1}^{ \lfloor \frac{A}{d} \rfloor} \sum \limits_{j = 1}^{ \lfloor \frac{B}{d} \rfloor} \sum \limits_{g | \gcd(i, j)} \mu(g)
\]
\]
拆开\(d | \gcd(i, j)\)：
\[\begin{aligned} & \sum \limits_{i = 1}^{ \lfloor \frac{A}{d} \rfloor} \sum \limits_{j = 1}^{ \lfloor \frac{B}{d} \rfloor} \sum \limits_{g | i, g | j} \mu(g) \\ =& \sum_{g = 1}^{ \min(A, B)} \mu(g) \lfloor \tfrac{A}{d} \rfloor\lfloor \tfrac{B}{d} \rfloor \end{aligned}
\]
\]
然后整除分块
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
const int N=1e6+10;
int vis[N],miu[N],pri[N],cnt;
inline void prework()
{
miu[1]=1;
for(int i=2;i<N;++i)
{
if(!vis[i]) pri[cnt++]=i,miu[i]=-1;
for(int j=0;j<cnt&&i*pri[j]<N;++j)
{
vis[i*pri[j]]=1; if(i%pri[j]) miu[i*pri[j]]=-miu[i];
else{miu[i*pri[j]]=0; break;}
} miu[i]+=miu[i-1];
}
return ;
}
signed main()
{
prework();
int a,b,d,ans=0; cin>>a>>b>>d;
a/=d; b/=d; if(a>b) swap(a,b);
for(int l=1,r,x,y;l<=a;l=r+1)
{
x=a/l; y=b/l;
r=min(a/x,b/y); ans+=x*y*(miu[r]-miu[l-1]);
} printf("%lld\n",ans);
return 0;
}
}
signed main(){yspm::main(); return 0;}