UVA 12169 Disgruntled Judge 枚舉+擴展歐幾裡得

題目大意：有3個整數 x[1], a, b 滿足遞推式x[i]=(a*x[i-1]+b)mod 10001。由這個遞推式計算出了長度為2T的數列，現在要求輸入x[1],x[3],......x[2T-1], 輸出x[2],x[4]......x[2T]. T<=100,0<=x<=10000. 如果有多種可能的輸出，任意輸出一個結果即可。

由於a和b都小於等於10000，直接枚舉a和b暴力可以過。但是有沒有更快的方法呢？

首先令遞推式的i=2，那麼x[2]=(a*x[1]+b)mod 10001；再令i=3，得x[3]=(a*x[2]+b)mod 10001，可以得出x[3]=(a*(a*x[1]+b)+b)mod 10001。這時候只有a和b是變數，我們枚舉a，就可以求出b了。(a+1)*b mod 10001 = ( (x[3]-a*a*x[1]) mod 10001 + 10001 ) mod 10001.(這裡的x[3]-a*a*x[1]可能為負，代碼中可以先不取模，後面計算b的時候一起取模即可) 所以簡化成(a+1)*b mod 10001 = (x[3]-a*a*x[1]) mod 10001。這裡就變成了同模方程，擴展歐幾裡得即可解答。

暴力代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=10000+5;
const int mod=10001;
int in[maxn];

int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    for(int i=0; i<t; i++)
        scanf("%d",in+i);
    bool flag;
    for(int a=0; a<=10000; a++)
    {
        for(int b=0; b<=10000; b++)
        {
            flag=false;
            for(int i=1; i<t; i++)
                if(in[i]!=((a*(a*in[i-1]%mod+b)+b)%mod))
                {
                    flag=true;
                    break;
                }
            if(!flag)
            {
                for(int i=0; i<t; i++)
                    printf("%d\n",(a*in[i]+b)%mod);
                break;
            }
        }
        if(!flag)
            break;
    }
    return 0;
}

擴展歐幾裡得：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=10000+5;
const int mod=10001;
int in[maxn];
typedef long long ll;

ll exgcd(ll a, ll b, ll&x, ll&y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll r = exgcd(b, a%b, y, x);
    ll t = x;
    y = y - a/b*t;
    return r;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    for(int i=0; i<t; i++)
        scanf("%d",in+i);
    bool flag;
    for(ll a=0; a<=10000; a++)
    {
        ll x,y;                     //定義long long 型是保證沒有取模的式子不會超記憶體
        ll g=exgcd(a+1,mod,x,y);
        ll tmp=in[1]-a*a*in[0];     //這裡可以先不取模，後面計算b的時候取模
        if(tmp%g==0)
        {
            flag=false;
            ll b=(x*tmp/g)%mod;     //這裡最好取下模，雖然後面計算in[i]的時候也會取模，但是算出來的in[i]可能因為b負太多而變成負數
            for(int i=1;i<t;i++)
            {
                if(in[i]!=(a*(a*in[i-1]+b)+b)%mod)
                {
                    flag=true;
                    break;
                }
            }
            if(!flag)
            {
                for(int i=0;i<t;i++)
                    printf("%d\n",(a*in[i]+b)%mod);
                break;
            }
        }

    }
    return 0;
}