POJ 2115 C Looooops(扩展欧几里得应用）-白红宇

POJ 2115 C Looooops(扩展欧几里得应用）

阅读量：5806 次

发布时间：2019-06-18

本文共 803 字，大约阅读时间需要 2 分钟。

题目地址：

水题。

。

公式非常好推。最直接的公式就是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 __int64LL 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;}