POJ - 2115 C Looooops（拓展欧几里得，解同余方程）

链接：POJ - 2115 C Looooops

题意：

一个C语言的for循环：

for(int i=A;i!=B;i+=C)st;

其中i表示变量，$A$、$B$和$C$分别表示初值、终值和步长，$st$表示循环体。
要求计算当循环变量i运算在k位无符号整数体系下（运算值范围：$0$ ~ $2^k?1$，此时，$i$+=$C$溢出后截断），循环体$st$会执行多少次？

分析：

设执行次数$x$，那么根据题意，则有：$A+xC\equiv B(\mathrm{m}\mathrm{o}\mathrm{d}{2}^k)$

即同余方程：$xC\equiv B?A(\mathrm{m}\mathrm{o}\mathrm{d}{2}^k)$

则同余方程可化为方程：$xC=B?A?y?2^k(y\in Z)$

$?xC+y?2^k=B?A$

化为：$ax+by=c$，其中$a=C,b=2^k,c=B?A$

拓展欧几里得解方程即可，解得特解$x_0$后，求得最小正整数解$x_{min}=(x_0\mathrm{m}\mathrm{o}\mathrm{d}t+t)\mathrm{m}\mathrm{o}\mathrm{d}t$
其中$t=\frac{b}{\gcd (a,b)}$

以下代码：

#include<cstdio>
#define LL long long
using namespace std;
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(b==0){
    x=1;y=0;d=a;}else{
    exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int main()
{
    LL A,B,C,k;LL a,b,c,d,x,y,t;while(scanf("%lld %lld %lld %lld",&A,&B,&C,&k)&&A+B+C+k){
    a=C;b=1LL<<k;c=B-A;exgcd(a,b,d,x,y);if(c%d!=0)printf("FOREVER\n");else{
    x=x*c/d;t=b/d;x=(x%t+t)%t;printf("%lld\n",x);}}return 0;
}