hdu 1695 GCD（容斥）

题目链接

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 /********************************************************************/

 const int maxn = 1e5+;

 vector<int> pri[maxn];

 //分解成的质数

 void init(){

     for(int i = ;i < maxn; i++){

         int now = i;

         for(int j = ;j*j <= now;j++){

             if(now%j == ){

                 pri[i].push_back(j);

                 while(now%j == ) now /= j;

             }

             if(now == ) break;

         }

         if(now > )

             pri[i].push_back(now);

     }

 }

 int solve(int x, int pos){

     int res = ;

     for(int i = ;i < ( << pri[x].size());i++){

         int num = ;

         int tmp = ;

         for(int j = ;j < pri[x].size();j++){

             if((i >> j)& ){

                 num++;

                 tmp *= pri[x][j];

             }

         }

         if(num & ) res += pos/tmp;

         else res -= pos/tmp;

     }

     return pos - res;

 }

 int main(){

     init();

     int t;

     t = read();

     for(int i = ;i <= t;i++){

         int a, b, c, d, k;

         //a = 1, d = 1;

         a = read(); b = read(); c = read(); d = read(); k = read();

         if(k == ){

             printf("Case %d: 0\n", i);

             continue;

         }

         b /= k, d /= k;

         if(b < d) swap(b, d);

         ll ans = ;

         for(int j = ;j <= b;j++){

             ans += solve(j, min(j, d));

         }

         printf("Case %d: %lld\n", i, ans);

     }

     return ;

 }