poj2115一次模余定理

2019-04-14 16:22发布

站内文章 / 模拟电子
16769 0 1473
http://poj.org/problem?id=2115 #include #include #include #include #include #include #include using namespace std; typedef __int64 INT ; INT ex_gcd( INT a , INT b , INT &x ,INT &y ) { if ( b == 0 ) { x = 1 ; y = 0 ; return a ; } else { INT tm = ex_gcd( b , a % b , x , y ) ; INT t = x ; x = y ; y = t - ( a / b ) * y ; return tm ; } } int main() { INT i , n , a1 ,r1 , a2 ,r2 ,ans , a , b , c , d , k , x0 , y0 ; while( scanf( "%I64d%I64d%I64d%I64d" , &a , &b , &c , &k ) , ( a + b + c + k ) ) { INT temp = c ; c = b - a ; a = temp ; b = ( INT )1 << k ; d = ex_gcd( a , b , x0 , y0 ) ; if( c % d != 0 ) { printf( "FOREVER " ) ; } else { INT ans = x0 * c / d ; INT temp = b / d ; ans = ( ans % temp + temp ) % temp ; printf( "%I64d " , ans ) ; } } return 0 ; }

热门文章