题目链接：acm.hdu.edu.cn/showproblem.php?pid=1695
GCD 素数+容斥原理#include<cstdio>#include<cstring>const int MAX=100010;__int64 eular[MAX];int num[MAX];int p[MAX][20];void init(){memset(eular,0,sizeof(eular));memset(num,0,sizeof(num));eular[1]=1;for(int i=2;i<MAX;i++){if(!eular[i]){for(int j=i;j<MAX;j+=i){if(!eular[j])eular[j]=j;eular[j]=eular[j]*(i-1)/i;p[j][num[j]++]=i;}}eular[i]+=eular[i-1];}}int RC(int n,int now,int t){int i;int sum=0;for(i=t;i<num[now];i++)sum+=n/p[now][i]-RC(n/p[now][i],now,i+1);return sum;}int main(){int t,T;int a,b,c,d,i,j,k,x;init();scanf("%d",&T);for(t=1;t<=T;t++){scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);if(k==0){printf("Case %d: 0\n",t);continue;}b/=k,d/=k;if(b>d){x=b;b=d;d=x;}__int64 sum=eular[b];for(i=b+1;i<=d;i++){sum+=b-RC(b,i,0);}printf("Case %d: %I64d\n",t,sum);}return 0;}
，我想去旅行，一个人背包，一个人旅行，
