UVa12169 - Disgruntled Judge(模演算)

UVa12169 - Disgruntled Judge(模运算)

如果知道了a，就能算出x2，根据x3=(ax2+b)mod10001算出b。
然后可在O(T)时间内计算出整个序列。
如果在计算中发现和输入矛盾，则a非法，因为a是0~10000的整数，即使枚举所有a，时间效率也足够高。
枚举a，利用x1，x3求出b，判断所有x的关系能不能满足a，b。

如何通过a，x1，x3求出b呢。
x2 = (a * x1 + b) % 10001;
x3 = (a * x2 + b) % 10001;
联立2个式子
x3 = (a * (a * x1 + b) % 10001 + b ) % 10001;
x3 = (a * (a * x1 + b) + b) % 10001;
所以 x3 + 10001 * k = a * a * x1 + (a + 1) * b;
x3 - a * a * x1 = (a + 1) * b + 10001 * (-k);
这样就成了求 b 和 -k，满足这个式子，不就是扩展欧几里得的一般用法么？

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<string>
#include<cmath>
#include<sstream>
#include<ctime>
using namespace std;
#define _PI acos(-1.0)
#define INF 1 << 10
#define esp 1e-6
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pill;

#define MAXD 200 + 10
#define max_size 10001
void gcd(LL a,LL b,LL &d,LL &x,LL &y){
    if(!b){
        d=a;
        x=1;y=0;
        return;
    }
    else {
        gcd(b, a%b, d, y, x);
        y -= x * (a/b);
        return ;
    }
}
int main()
{
    LL a,b,x[MAXD];
    int T;
    scanf("%d",&T);
    for(int i=1;i<2*T;i+=2)
        scanf("%lld",&x[i]);
    for(a=0;;a++){
        LL k, b, d;
        LL t = (x[3]-a*a*x[1]);
        gcd(max_size, a+1, d, k, b);
        if(t % d) continue;
        b = b * t / d;
        int yes = 1;
        for(int i=2;i<=2*T;i++){
            if(i&1){
                if(x[i]!=((a*x[i-1]+b)%max_size)){
                    yes=0;
                    break;
                }
            }
            else {
                x[i]=(a*x[i-1]+b)%max_size;
            }
        }
        if(yes)
            break;
    }
    for(int i=2;i<=2*T;i+=2)
        printf("%lld\n",x[i]);
    return 0;
}

UVa12169 - Disgruntled Judge(模演算)

相关推荐