[POJ 2115} C Looooops 题解（扩展欧几里德）

题目描述

对于C的for(i=A ; i!=B ;i +=C)循环语句，给出A,B,C和k(k表示变量是在k进制下的无符号整数),判断循环次数,不能终止输出"FOREVER".

输入

多组数据，每组一行，A,B,C,k

程序以0 0 0 0结束

输出

一行一个整数，表示循环次数，或者"FOREVER"

样例输入

3 3 2 16

3 7 2 16

7 3 2 16

3 4 2 16

0 0 0 0

样例输出

0

2

32766

FOREVER

这道题翻译一下就是扩展欧几里得解方程，我们知道ax=c(mod p)可以转化为ax+py=c，最后将x，y乘上c/gcd(a,b)就是答案了

这里有一点要注意..答案如果为负要取到最小的正整数解。

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

ll exgcd(ll a,ll b,ll &x,ll &y)

{

    if(b==)

    {

        x=;

        y=;

        return a;

    }

    ll ans=exgcd(b,a%b,x,y);

    ll temp=x;

    x=y;

    y=temp-a/b*y;

    return ans;

}

int main()

{

    ll a,b,c,d,k,A,B,C,X,Y;

    while()

    {

        cin>>a>>b>>c>>k;

        if(a==&&b==&&c==&&k==)

        break;

        C=b-a;

        A=c;

        B=(ll)<<k;

        if(C<)

        {

            C+=B;

        }

        d=exgcd(A,B,X,Y);

        if(C%d!=)

        {

            printf("FOREVER\n");

        }

        else

        {

            ll t=B/d;

            ll ans=(X*C/d)%B;

            ans=(ans%t+t)%t;

            cout<<ans<<endl;

        }

    }

}