[poj 2115]C Looooops[擴展歐幾裡德][模線性方程]

題意:

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]***,解釋如下:

因為求得的解的含義是"步數",所以要模"步數對應的周期".

#include <cstdio>
using namespace std;
typedef long long ll;

ll Extended_Euclid(ll a, ll b, ll &x, ll &y)
{
    if(!b)
    {
        x = 1;
        y = 0;//無關變量取0方便計算,求模之後無影響
        return a;
    }
    ll r = Extended_Euclid(b, a%b, x, y);
    ll t = x;
    x = y;
    y = t - a/b*y;
    return r;
}

ll Modular_Linear_Equation(ll a, ll b, ll n)
{
    ll x, y, e;
    ll d = Extended_Euclid(a, n, x, y);
    if(b % d)   return -1;
    e = x*b/d % n + n;//轉化為正數,要先取模再加
    return e % (n/d);//***
}

int main()
{
    ll a,b,c,ans;
    int k;

    while(scanf("%lld %lld %lld %d",&a,&b,&c,&k) && (a+b+c+k))
    {
        ans = Modular_Linear_Equation(c, b-a, ((ll)1)<<k);
        if(ans == -1)
            puts("FOREVER");
        else
            printf("%lld\n",ans);
    }
}