【题解】UVa 12169【Disgruntled Judge】

背景

数论第二题

分析

发现可以暴力,那就暴力枚举就好了,正解是拓展欧几里得算法

代码

#include<cstdio>

const int MAXN = 666,MOD = 10001;
int X[MAXN];

int main(){
    int t;scanf("%d",&t);
    for(int i = 1;i < 2 * t;i += 2) scanf("%d",&X[i]);
    bool running;
    for(int a = 0;a < MOD;a++){
        for(int b = 0;b< MOD;b++){
            running = true;
            for(int i = 2;i <= 2 * t;i++){
                if(i & 1){//奇数 
                    if(X[i] != ((a * X[i - 1] + b) % MOD)){running = false;break;}
                }else{
                        X[i] = (a * X[i - 1] + b) % MOD;
                }
            }
            if(running) break;
        }
        if(running) break;
    }
    for(int i = 2;i <= 2 * t;i += 2) printf("%d\n",X[i]);

    return 0;
}