1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| int a,b,c,d,k;
int prime[N],pre[N],mu[N],kp; bool Is_or[N]; void Prime(){ kp = 0; memset(Is_or,true,sizeof(Is_or)); Is_or[0]=Is_or[1]=0; mu[1]=pre[1]=1; for(int i=2;i<=50000;i++){ if(Is_or[i]) mu[i]=-1,prime[kp++]=i; for(int j=0;j<kp&&prime[j]*i<=50000;j++){ Is_or[prime[j]*i]=0; if(0==i%prime[j]) {mu[prime[j]*i]=0;break; } mu[prime[j]*i] = -mu[i]; } pre[i]=pre[i-1]+mu[i]; } return ; }
int calc(int x,int y){ x/=k,y/=k; if(x>y) x^=y,y^=x,x^=y; int ans = 0; for(int i=1,pos;i<=x;i=pos+1){//分块优化 pos = min(x/(x/i),y/(y/i)); ans+=(pre[pos]-pre[i-1])*(x/i)*(y/i); } return ans ; }
void work(){ scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); printf("%d\n",calc(b,d) -calc(a-1,d) -calc(b,c-1) +calc(a-1,c-1)); }
int main(){ Prime(); int _ = 1; //while(~scanf("%d",&_)) scanf("%d",&_); while(_--) work();
return 0; }
|