C Looooops Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 23388   Accepted: 6443 Description A Compiler Mystery: We are given a C-language style for loop of type 
for (variable = A; variable != B; variable += C) statement;
I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values 0 <= x < 2k) modulo 2k. 

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. 

The input is finished by a line containing four zeros. 
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 题目链接：http://poj.org/problem?id=2115
好久没碰扩欧了，上个题还是青蛙的约会。 数论其实难点并不在于知识点上，而是应用上，这是我学了扩欧和反演得出来的结论，你就像这个题，我一开始根本就没往扩欧上想，看了题解才明白，哦，就是个简单的扩欧，裸地求解模线性方程，题解上的式子一看就看懂了，也不是不会，就是想不到，愁人啊。努力把，渣渣。 题目要用到的最重要的知识点就是扩展欧几里得，不会的先去学习，我博客里就有 http://blog.csdn.net/bless924295/article/details/51397730 扩欧其实挺好懂得，式子推一推就出来了。 题意不难理解，只是利用了 k位存储系统 的数据特性进行循环。例如int型是16位的，那么int能保存2^16个数据，即最大数为65535（本题默认为无符号），当循环使得i超过65535时，则i会返回0重新开始计数如i=65534，当i+=3时，i=1其实就是 i=(65534+3)%(2^16)=1   有了这些思想，设对于某组数据要循环x次结束，那么本题就很容易得到方程： x=[(B-A+2^k)%2^k] /C 即 Cx=(B-A)(mod 2^k)  此方程为 模线性方程，本题就是求X的值。（是不是很熟悉）
令a=C  b=B-A n=2^k 那么原模线性方程变形为：   ax=b (mod n) 该方程有解的充要条件为 gcd(a,n) | b ，即 b% gcd(a,n)==0 令d=gcd(a,n) 有该方程的 最小整数解为 x = e (mod n/d) 其中e = [x0 mod(n/d) + n/d] mod (n/d) ，x0为方程的最小解 那么原题就是要计算b% gcd(a,n)是否为0，若为0则计算最小整数解，否则输出FOREVER。
注意此题要用long long
代码： #include #include #include using namespace std; long long exGCD(long long a,long long b,long long &x,long long &y)//扩欧的板子 { if(b==0) { x=1; y=0; return a; } long long d=exGCD(b,a%b,x,y); long long tmp=x; x=y; y=tmp-a/b*y; return d; } int main() { long long A,B,C,K; while(cin>>A>>B>>C>>K) { if(!A&&!B&&!C&&!K) break; long long a=C; long long b=B-A; long long n=(long long)1<
附上我当时学扩欧时大神的网址： http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

上面的扩欧的非递归写法我到现在也没看懂。。。 我的板子就是这个