HDU 1695 GCD (容斥原理+质因数分解) - c++编程基础

先进行预处理，对每一个数分解质因数。

然后将因为若gcd(x,y)==z,那么gcd(x/z,y/z)==1，又因为不是z的倍数的肯定不是，所以不是z的倍数的可以直接去掉，所以只要将b和d除以k，然后就转化成了求两个范围中互质的对数了。这时候可以枚举1~b，然后用容斥原理找1~d范围内的与枚举数互质的数的个数，为了避免重复，只要再限定下大小关系就可以了，具体见代码。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            using namespace std; #define LL __int64 const int mod=1e9+7; const int INF=0x3f3f3f3f; LL ans; LL a, b, c, d; vector
           
            vec[110000]; void dfs(LL i, int cur, int cnt, LL tmp) { tmp*=(LL)vec[i][cur]; if(cnt&1) { ans+=(LL)min(d,i)/tmp; } else { ans-=(LL)min(d,i)/tmp; } for(int j=cur+1; j
            
             1) vec[i].push_back(x); } } int main() { int t, i, j, num=0; LL sum, k; init(); scanf("%d",&t); while(t--) { scanf("%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&k); num++; if(!k) { printf("Case %d: 0\n",num); continue ; } b/=k; d/=k; if(b