题意

\(T\le 10^4\) 次询问 \(n,m\) ，求

\[\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)\text { is prime}]
\]

分析

这题还是很有趣的。设 \(n\le m\) 。

\[\begin{aligned}
\sum _{i=1}^n\sum_{j=1}^m[gcd(i,j)\text { is prime}]&=\sum _{i=1}^n\sum _{j=1}^m\sum _k [k\text { is prime}][gcd(i,j)=k] \\
&=\sum _{i=1}^n\sum _{j=1}^m\sum _{k|i,k|j}[k\text { is prime}]\sum _{d|\frac{i}{k},d|\frac{j}{k}}\mu(d) \\
&=\sum _{d=1}^n\mu (d)\sum _{k=1}^n[k\text { is prime}]\sum _{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum _{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|i,d|j] \\
&=\sum _{d=1}^n\mu (d)\sum _{k=1}^n[k\text { is prime}]\lfloor\frac{n}{kd}\rfloor \lfloor\frac{m}{kd}\rfloor \\
&=\sum _{i=1}^n\lfloor\frac{n}{i}\rfloor \lfloor\frac{m}{i}\rfloor\sum _{k|i,k\text { is prime}}\mu(\frac{i}{k})
\end{aligned}
\]

令 \(f(x)=\sum _{k|x,k\text {is prime }}\mu (x/k)\) ，我们有：

\[ans=\sum _{i=1}^n\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor f(i)
\]

\(f(x)\) 可以在线性筛的过程中顺便处理出来，求前缀和就可以做到每次询问 \(O(\sqrt n)\) 。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long giant;

inline int read() {

	int x=0,f=1;

	char c=getchar_unlocked();

	for (;!isdigit(c);c=getchar_unlocked()) if (c=='-') f=-1;

	for (;isdigit(c);c=getchar_unlocked()) x=x*10+c-'0';

	return x*f;

}

const int maxn=1e7+1;

bool np[maxn];

int p[maxn],ps=0,mu[maxn],f[maxn];

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

#endif

	mu[1]=1,f[1]=0;

	for (int i=2;i<maxn;++i) {

		if (!np[i]) p[++ps]=i,mu[i]=-1,f[i]=1;

		for (int j=1,tmp;j<=ps && (tmp=i*p[j])<maxn;++j) {

			np[tmp]=true;

			if (i%p[j]) mu[tmp]=-mu[i],f[tmp]=mu[i]-f[i]; else {

				mu[tmp]=0;

				f[tmp]=mu[i];

				break;

			}

		}

	}

	for (int i=2;i<maxn;++i) f[i]+=f[i-1];

	int T=read();

	while (T--) {

		int n=read(),m=read();

		if (n>m) swap(n,m);

		giant ans=0;

		for (int i=1,j;i<=n;i=j+1) {

			j=min(n/(n/i),m/(m/i));

			ans+=(giant)(f[j]-f[i-1])*(n/i)*(m/i);

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

bzoj2820-GCD

题意

分析

代码

最新文章

热门文章