设为首页 加入收藏

TOP

HDU 1695 GCD 欧拉函数+容斥原理+质因数分解
2015-07-20 17:58:08 来源: 作者: 【大 中 小】 浏览:3次
Tags：HDU 1695 GCD 函数 容斥 原理 因数分解

?

题意：在[a,b]中的x，在[c,d]中的y，求x与y的最大公约数为k的组合有多少。（a=1, a <= b <= 100000, c=1, c <= d <= 100000, 0 <= k <= 100000）

思路：因为x与y的最大公约数为k，所以xx=x/k与yy=y/k一定互质。要从a/k和b/k之中选择互质的数，枚举1~b/k，当选择的yy小于等于a/k时，可以选择的xx数为Euler(yy),当yy大于a/k时，就要用容斥原理来找到yy的质因数，在a/k范围内找到与yy互质的数。

代码：

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
       #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #define PI acos(-1.0) #define maxn 1<<20 #define INF 0x7fffffff #define eps 1e-8 typedef long long LL; typedef unsigned long long ULL; using namespace std; LL ans=0; LL S=0; LL sum2; LL euler[100050]; void init() { memset(euler,0,sizeof(euler)); euler[1] = 1; for(int i = 2; i <= 100000; i++) if(!euler[i]) for(int j = i; j <= 100000; j += i) { if(!euler[j]) euler[j] = j; euler[j] = euler[j]/i*(i-1); } } void factor(int n,int a[maxn],int b[maxn],LL &tt) { int temp,i,now; temp=(int)((double)sqrt(n)+1); tt=0; now=n; for(i=2; i<=temp; i++) { if(now%i==0) { a[++tt]=i; b[tt]=0; while(now%i==0) { ++b[tt]; now/=i; } } } if(now!=1) { a[++tt]=now; b[tt]=1; } } int dfs(int aa[],int pos,int res,int sum,int b,int tot)//res乘积，sum乘数的个数 { if(pos+1<=tot) dfs(aa,pos+1,res,sum,b,tot); sum++; res*=aa[pos]; if(sum%2) sum2+=b/res; else sum2-=b/res; if(pos+1<=tot) dfs(aa,pos+1,res,sum,b,tot); return 0; } int main() { int T,tt=0,aa[40],bb[40]; init(); while(~scanf(%d,&T)) { tt=0; while(T--) { tt++; int a,b,c,d,k; scanf(%d%d%d%d%d,&a,&b,&c,&d,&k); printf(Case %d: ,tt); if(k==0) { printf(0 ); continue; } if(d
                
                 
?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：c++内存泄漏处理（积累） 下一篇：poj3080Blue Jeans

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: