poj2115 同余方程与扩展欧几里得

题目意思给出A,B,C，问对于C语句语句

for (variable = A; variable != B; variable += C)
  statement;

循环的次数，如果是死循环，就输出FOREVER 。其中数据都在$2^k$内，且都为非负数,也就是说当数据大于$2^k$时就要对$2^k$取模

这题题目意思很好理解，细细观察发现假设循环执行了$t$次，则会有 $(A + Ct ) = B \bmod 2 ^ k$ 题目就是要求的最小的非负数$t$ 。

对于同余方程的解法，可以参考http://www.cnblogs.com/ACShiryu/archive/2011/08/03/2126676.html

题目数据虽然都是32位，但在中间算的时候有可能超int 故要用__int64 刚开始没注意到，WA了2次，有一次是对1左移时没强制转换。

poj2115 C Looooopsview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
void gcd ( __int64 a , __int64 b , __int64 &d , __int64 &x ,__int64 &y )
{
    if ( ! b ) 
        d = a , x = 1 , y = 0 ;
    else
        gcd ( b , a % b , d , y , x ) , y -= x * ( a / b ) ;
}
int main()
{
    __int64 a, b , c, k ;
    while ( cin >> a >> b >> c >> k , a || b || c || k )
    {
        __int64 d , x , y ;
        gcd ( c ,  ( ( __int64 ) 1 )<< k , d , x , y ) ;
        if ( ( b - a ) % d != 0 )
            cout << "FOREVER" <<endl;
        else
        {
            __int64 ans = ( b - a ) / d * x ;
            ans = ans % ( (  ( ( __int64 ) 1 )<< k ) / d ) ;
            if ( ans < 0 )
                ans += (  ( ( __int64 ) 1 )<< k ) / d ;
            cout << ans << endl ;
        }
    }
    return 0;
}