P2257 YY的GCD

标签：lfloor mu frac GCD int P2257 tot YY fo

传送门
首先得到一个非常显然的柿子

\[\sum_{p} \sum_{d} \lfloor\frac{n}{pd}\rfloor \lfloor\frac{m}{pd}\rfloor \]

我们可以考虑T=pd，然后转化柿子

\[\sum _{T} \lfloor\frac{n}{T} \rfloor \lfloor\frac{m}{T} \rfloor \sum_{p|T}\mu(\frac{T}{p}) \]

后面这一块可以预处理。然后就是经典的分块，为什么要设T=pd，是因为我们如果你枚举的是p，那么你的d还是要分块，受到n,m的制约，而将其看为一个整体之后我们就可以预处理跟n，m无关的信息，从而快速回答询问。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef long long ll;
const int N=1e7+5;
int p[N],tot,f[N],mu[N];
int t[N],n,m,j,k;
ll ans;
bool vis[N];

int main(){
//	freopen("data.in","r",stdin);
	mu[1]=1;
	fo(i,2,N-1){
		if (!vis[i]) {
			f[i]=i-1;
			mu[i]=-1;
			p[++tot]=i;
		}
		fo(j,1,tot) {
			if ((ll)i*(ll)p[j] >= N) break;
			vis[i*p[j]]=1;
			if (i%p[j]==0) {
				f[i*p[j]]=f[i]*p[j];
				break;
			}
			else {
				f[i*p[j]]=f[i]*(p[j]-1);
				mu[i*p[j]]=-mu[i];
			}
		}	
	}
	
	fo(i,1,tot) {
		fo(j,1,(N-1)/p[i]) { 
			t[p[i]*j]+=mu[j];
		}
	}
	fo(i,1,N-1) t[i]+=t[i-1];
	
	
	int Q;
	scanf("%d",&Q);
	while (Q--){
		scanf("%d %d",&n,&m);
		
		ans=0;
		j=1;
		while (j<=min(n,m)) {
			k=min(n/(n/j), m/(m/j));
			ans+=(ll)(n/j)*(ll)(m/j)*(ll)(t[k]-t[j-1]);
			j=k+1;
		}
		printf("%lld\n",ans);
	
	}
	
	return 0;
}

标签：lfloor,mu,frac,GCD,int,P2257,tot,YY,fo
From： https://www.cnblogs.com/ganking/p/17594424.html