设为首页 加入收藏

TOP

POJ 2115 C Looooops(扩展欧几里得应用)
2015-07-20 17:58:51 来源: 作者: 【 】 浏览:2
Tags:POJ 2115 Looooops 扩展 欧几 应用

题目地址:POJ 2115

水题。。公式很好推。最直接的公式就是a+n*c==b+m*2^k.然后可以变形为模线性方程的样子,就是

n*c+m*2^k==b-a.即求n*c==(b-a)mod(2^k)的最小解。(真搞不懂为什么训练的时候好多人把青蛙的约会都给做出来了,这题却一直做不出来。。。。。这两道不都是推公式然后变形吗。。。。。)

代码如下:

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define LL __int64 LL X, Y; LL exgcd(LL a,LL b) { if(b==0) { X=1; Y=0; return a; } LL r=exgcd(b,a%b); LL t=X; X=Y; Y=t-a/b*Y; return r; } int main() { LL a, b, c, k, d, L, z; while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&k)!=EOF&&k) { z=pow(2,k); d=exgcd(c,z); L=b-a; if(L%d) { printf("FOREVER\n"); continue ; } else { LL ans=X*L/d; LL s=z/d; if(ans<0) { ans=ans%s+s; } else { ans=ans%s; } printf("%I64d\n",ans); } } return 0; }
            
           
         
        
       
      
     
    
   
  


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇杭电 2188(博弈 水题 巴什博弈) 下一篇HDU 3008 Warcraft

评论

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