JZYZOJ1518 [haoi2011]b 莫比乌斯反演 分块 容斥
http://172.20.6.3/Problem_Show.asp?id=1518
最开始只想到了n^2的写法，肯定要超时的，所以要对求gcd的过程进行优化。
首先是前缀和容斥，很好理解。
第二个优化大致如下：
u为莫比乌斯函数，t为gcd(x,y)为i的倍数的数的个数；
满足gcd(x,y)=1的数字对的数量=sigma(1<=i<=min(x,y))u[i]*t[i];
t[i]=(x/i)*(y-i);
由小数向下取整可知有连续的i满足x/i为定值，y/i也是定值，所以可以分块计算，用u[i]的前缀和*定值，加快求gcd(x,y)=1的对数的速度。
代码
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<iostream> 6 using namespace std; 7 const int maxn=50010; 8 int n; 9 int a,b,c,d,k; 10 bool vis[maxn]={}; 11 int ur[maxn]={},su[maxn]={},sum[maxn]={},tot=0; 12 void doit(){ 13 sum[1]=1;ur[1]=1; 14 for(int i=2;i<maxn;i++){ 15 if(!vis[i]){ur[i]=-1;su[++tot]=i;} 16 for(int j=1;j<=tot&&i*su[j]<maxn;j++){ 17 int z=i*su[j];vis[z]=1; 18 if(i%su[j]==0)break; 19 ur[z]=ur[su[j]]*ur[i]; 20 } 21 sum[i]=sum[i-1]+ur[i]; 22 } 23 } 24 int getit(int x,int y){ 25 int z=0,nex=0; 26 if(x>y)swap(x,y); 27 for(int i=1;i<=x;i=nex+1){ 28 int xx=x/i,yy=y/i; 29 nex=min(x/xx,y/yy); 30 z+=(sum[nex]-sum[i-1])*xx*yy; 31 } 32 return z; 33 } 34 int main(){ 35 doit();int ans=0; 36 scanf("%d",&n); 37 while(n-->0){ 38 scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); 39 a-=1;c-=1; 40 a/=k;b/=k;c/=k;d/=k; 41 ans=0;ans+=getit(b,d);ans-=getit(b,c);ans-=getit(a,d);ans+=getit(a,c); 42 printf("%d ",ans); 43 } 44 return 0; 45 }