题意:
for (variable = A; variable != B; variable += C)
statement;
给出A,B,C和k(k表示变量是在k位机下的无符号整数),判断循环次数,不能终止输出"FOREVER".
思路:
需要求解 (A + x * C) % mod = B
变形之后即 C * x + mod * y = B - A = gcd(C , mod) * [ (B - A) / gcd(C , mod) ]
用扩展欧几里德定理 需要求 C * x + mod * y = gcd(C , mod)
a = C, b = mod
即模线性方程
需要注意的是: 把模线性方程求得的特解转化为正数之后,要模 b/gcd(a,b) [而不是b]***,解释如下:
因为求得的解的含义是"步数",......
阅读全文