Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you're only required to output the total number of different number pairs.

Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.

Yoiu can assume that a = c = 1 in all test cases.

 

容斥原理的裸题

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 typedef long long ll; 7  8 const int maxn=2e5+5; 9 10 int pnum[maxn][30],num[maxn];11 12 void init(){13     memset(pnum,0,sizeof(pnum));14     memset(num,0,sizeof(num));15     for(int i=2;i<=100100;++i){16         if(!num[i]){17             pnum[i][++num[i]]=i;18             for(int j=2;i*j<=100100;++j){19                 pnum[i*j][++num[i*j]]=i;20             }21         }22     }23 }24 25 int main(){26     init();27     int T;28     scanf("%d",&T);29     for(int q=1;q<=T;++q){30         int a,b,c,d,k;31         scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);32         if(!k){33             printf("Case %d: 0\n",q);34             continue;35         }36         a=b/k;b=d/k;37         if(a>b){c=a;a=b;b=c;}38         ll ans=0;39         if(a>=1)ans+=b;40         for(int p=2;p<=a;++p){41             ll res=0;42             for(int i=1;i<(1<