POJ 2115 简单的模线性方程求解

简单的扩展欧几里得题

这里 2^k 不能自作聪明的用 1<<k来写 ， k >= 31时就爆int了 ， 即使定义为long long 也不能直接这样写

后来老老实实 for(int i=1 ; i<=k ; i++) bb = bb*2; 才过了= =

 #include <cstdio>

 #include <cstring>

 using namespace std;

 #define ll long long

 ll ex_gcd(ll a , ll &x , ll b , ll &y)

 {

     if(b == ){

         x =  , y = ;

         return a;

     }

     ll ans = ex_gcd(b , x , a%b , y);

     int t = x;

     x = y , y = t - a/b*y;

     return ans;

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     int a , b , c , k;

     while(scanf("%d%d%d%d" , &a , &b , &c , &k)){

         if(a ==  && b ==  && c ==  && k == ) break;

         ll aa = c , bb =  , cc = b-a , x , y;

         for(int i= ; i<=k ; i++) bb = bb*;

         ll g = ex_gcd(aa , x , bb , y);

         if(cc % g != ){

             puts("FOREVER");

             continue;

         }

         ll kk = cc / g;

         x*=kk , y*=kk;

         aa/=g , bb/=g;

         if(x >= )

             x = x - x/bb*bb;

         else

             x = x - x/bb*bb+bb;

         printf("%I64d\n" , x);

     }

     return ;

 }