2024-03-28

news/发布时间2024/5/1 5:21:15

2024-03-28

\({\color{Red}\Large到成都集训来了!}\)

晚上自习

YY的GCD

\({\color{Chocolate}Problem}\)
\(i\in[1,n],j\in[1,m] \ \ \ m,n\le10^7\)，\(T\le10^4\) 组询问，求 \(\gcd(i,j)\) 是素数的 \((i,j)\) 对数

\({\color{Chocolate}Solution}\)

\[\begin{align*} ans&=\sum_{p\in primes}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=p]\newline &=\sum_{p\in primes}\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}[\gcd(i,j)=1] \end{align*} \]

莫比乌斯函数有一个小性质

\[\sum_{d\mid x}\mu(d)=[x=1] \]

\[\therefore[gcd(i,j)=1]=\sum_{d\mid\gcd(i,j)}\mu(d) \]

\[\therefore ans=\sum_{p\in primes}\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}\sum_{d\mid\gcd(i,j)}\mu(d) \]

考虑改变求和顺序
先枚举 \(k=\gcd(i,j)\)，则 \(i,j\) 均是 \(k\) 的倍数

\[ans=\sum_{p\in primes}\sum_{k=1}^{\min(\left\lfloor\frac{n}{p}\right\rfloor,\left\lfloor\frac{m}{p}\right\rfloor)}\sum_{d\mid k}\mu(d)\times\left\lfloor\frac{n}{pk}\right\rfloor\times\left\lfloor\frac{m}{pk}\right\rfloor \]

接下来（按照题解说的）是常见的变换方式
设 \(t=pk\)

\[\begin{align*} ans&=\sum_{p\in primes}\sum_{k=1}^{\min(\left\lfloor\frac{n}{p}\right\rfloor,\left\lfloor\frac{m}{p}\right\rfloor)}\sum_{d\mid k}\mu(d)\times\left\lfloor\frac{n}{t}\right\rfloor\times\left\lfloor\frac{m}{t}\right\rfloor\newline &=\sum_{t=1}^{\min(n,m)}\left\lfloor\frac{n}{t}\right\rfloor\times\left\lfloor\frac{m}{t}\right\rfloor\sum_{p\in primes,p\mid t} \mu(\frac{t}{p}) \end{align*} \]

\(k\) 的约数不用再枚举的原因是：\(t\) 实际上枚举的是 \(p\)和 \(k\)的所有约数的乘积，已经考虑过了

最后面的和式可以在线性筛的时候预处理
剩下的数论分块

时间复杂度 \(O(n+T\sqrt{n})\)

\({\color{Chocolate}Code}\)

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;typedef long long ll;const int N=1e7+100;ll n,m;int primes[N],cntp;
bool st[N];
int mu[N];
ll sm[N];void init_mu(int mx) {mu[1]=1;for(int i=2;i<=mx;i++) {if(!st[i]) primes[++cntp]=i,mu[i]=-1;for(int j=1;i*primes[j]<=mx;j++) {st[i*primes[j]]=true;if(i%primes[j]==0) {mu[i*primes[j]]=0;break;}mu[i*primes[j]]=-mu[i]; }}for(int j=1;j<=cntp;j++)for(int i=1;i*primes[j]<=mx;i++)sm[i*primes[j]]+=mu[i]*1ll;for(int i=1;i<=mx;i++) sm[i]+=sm[i-1];
}int main() {init_mu(1e7+10);int T;scanf("%d",&T);while(T--) {scanf("%lld%lld",&n,&m);if(n>m) swap(n,m);ll lft=1,rgh,ans=0;while(lft<=n) {rgh=min(n,min(n/(n/lft),m/(m/lft)));ans+=(sm[rgh]-sm[lft-1])*(n/lft)*(m/lft);lft=rgh+1;}printf("%lld\n",ans); }return 0;
}