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

TOP

HDU 1695 GCD (容斥原理+质因数分解)

2015-07-20 17:24:38 来源: 作者: 【大中小】浏览:2次

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

然后将因为若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


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu 1713 相遇周期（GCD & L..	下一篇：NYOJ 476 谁是英雄(唯一素因子分..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: