题目不难，设计到的知识点也不多。具体为扩展欧几里德定理求解模线性方程。题意为给定一个循环： for (variable = A; variable != B; variable += C) statement; A、B、C为K bit无符号数（即0<=A、B、C<2^k)。要我们判段该循环内的statement可以执行多少次，若为死循环。则输出FOREVER。 若不为死循环。且假定可以循环X次。则可以推出: (A+X*C)%(2^K)=B也即X*C=(B-A)%(2^K)。此式子为模线性方程。若方程有解则求出该方程的最小整数。否则说明为死循环，输出FOREVER。那么关键点就是求解模线性方程了。 令a=C;     b=B-A;     n=2^K; 模线性方程如下：ax=b(mod)n; 下面介绍利用扩展欧几里德算法求解ax=b(mod)n即方程：ax+ny=b; 首先：ax=b(mod)n;若有解则说明GCD(a,n)|b,即b%GCD(a,n)==0.解个数为GCD(a,n)，否则无解。若存在解，则令d=GCD(a,n)，利用扩展欧几里德算法求解ax+ny=d的一个解x0,y0. 满足ax0+ny0=d, 两边同时乘以b/d,则为a*b/d*x0+n*b/d*y0=b; 则模线性方程ax=b(mod)n的最小解为：x0'=x=(b/d)*x0，y0'=(b/d)*y0。d个解如下： xi= x0'+ i* (n/ d ){i= 0... d-1}。 设ans=x0‘*(b/d),s=n/d; 方程ax≡b (mod n)的最小整数解为：(ans%s+s)%s; 那么关键点就是扩展欧几里德算法的编写了：下面是其递归模板（理解为主），在我的博客中有介绍： 01.int exgcd(int a,int b,int &x,int &y){ 02. if(b==0){ 03. x=1; 04. y=0; 05. return a; 06. } 07. int r=exgcd(b,a%b,x,y); 08. int t=y; 09. y=x-(a/b)*y; 10. x=t; 11. return r; 12.} 如下为其非递归形式： 01.int exgcd(int a,int b,int &x,int &y){ 02. if(b==0){ 03. x=1; 04. y=0; 05. return a; 06. } 07. int q,r; 08. int x1=0,y1=1; 09. int x2=1,y2=0; 10. while(b>0){ 11. q=a/b; 12. r=a-q*b; 13. x=x2-q*x1; 14. y=y2-q*y1; 15. a=b; 16. b=r; 17. x2=x1; 18. x1=x; 19. y2=y1; 20. y1=y; 21. } 22. x=x2,y=y2; 23. return a; 24.} 还需要注意的就是再求最小整数解时。由于最小解可能小于0，故要对其先求模，然后再取模。另外表示2^k，若为int,则直接为1<#include #include __int64 A,B,C; int k; __int64 exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y){ // 扩展欧几里德算法求解方程ax+ny=b的最小解x0,y0 if(b==0){ x=1,y=0; return a; } __int64 rs=exgcd(b,a%b,x,y); __int64 temp=x; x=y; y=temp-a/b*y; return rs; } int main(){ while(scanf("%I64d%I64d%I64d%d",&A,&B,&C,&k)){ if(A==0 && B==0 && C==0 && k==0) break; __int64 n=(__int64)1<