Description
A Compiler Mystery: We are given a C-language style for loop of typefor (variable = A; variable != B; variable += C) statement;
Input
The input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 <= k <= 32) is the number of bits of the control variable of the loop and A, B, C (0 <= A, B, C < 2k) are the parameters of the loop.Output
The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate.Sample Input
3 3 2 16 3 7 2 16 7 3 2 16 3 4 2 16 0 0 0 0
Sample Output
0 2 32766 FOREVER
Source
題目大意初始值是a,每一次加c ,可以對得到的值取模2^k,在值為b時結束,問最少會執行多少次,如過一直不會停FOREVER
由題中大意的到等式,假設一定會停,那麼在循環x次後會等於b 也就是 (a + x*c)% (2^k)= b 。很明顯的擴展gcd的題目,得到等式, a + c*x - b = y*(2^k) 也就是
求解 c*x - (2^k)*y = b-a ,問有沒有整數解。
對於a*x1 + b*y1 = c ,用擴展gcd,求解 a*x1 + b*y1 = gad(a,b) = gcd(b,a%b) = a*y2 +b* (x2-a/b*y2)得到 x1 = y2 , y1 = ( x2 +a/b*y2 ) , 利用這個等式,可以推到b = 0 時,那是x = 1 , y = 0 ,最大公約數為a,在逐層返回,最終得到 a*x1 + b*y1 = gad(a,b) 的解,如果c%( gcd(a,b) ) == 0 那麼a*x1 + b*y1 = c有整數解,令d = gcd(a,b),d = b / d.最小的正整數解圍 x = ( x%d +d )%d.
#include#include #include #define LL __int64 using namespace std; void gcd(LL a,LL b,LL &d,LL &x,LL &y) { if(b == 0) { d = a ; x = 1 ; y = 0 ; } else { gcd(b,a%b,d,y,x); y = -y ; x = -x ; y += a/b*x ; } return ; } int main() { LL k , a , b , c , d , x , y ; while(scanf("%I64d %I64d %I64d %I64d", &a, &b, &c, &k)!=EOF) { if(a == 0 && b == 0 && c == 0 && k == 0) break; k = ( (LL)1 )<