【UVA12169】不爽的裁判

题意

随机选取x₁,a,b，根据公式xi=(a*x_i-1+b)%10001得到一个长度为2*n的序列，奇数项作为输入，求偶数项，若有多种，随机输出一组答案

即，给出已知的x₁，x₃，x₅，x₇……x_2k+1，找出a和b，满足递推式，并输出x₂，x₄，x₆……x_2k  (n0<=a,b<=10000)

分析

据说暴力也能过？？？告辞。

题目上说找出a和b这个很像是解方程，于是尝试转换一下条件吧。

x₂=(a*x₁+b)%10001

x₃=(a*x₂+b)%10001  ---> x3=(a*((a*x₁+b)%10001)+b)%10001

x₃=(a*(a*x₁+b)+b)%10001

将x₃看成a*(a*x₁+b)+b除以y的余数

则有 x₃+y*10001=a*a*x₁+a*b+b=a*a*x₁+(a+1)*b

再移项 x₃-a*a*x₁ =(a+1)*b-y*10001 

这个式子是不是很眼熟？假设a为已知，而x₁和x₃本来就已知，则就是一个关于y和b的二元一次不定方程嘛

用扩展欧几里得求解，需要验证一下x₃-a*a*x₁是不是gcd(a+1,10001)的倍数

于是枚举a，求出b，再用奇数项验证

代码

#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define mod 10001
#define RT register
#define ll long long
ll n,a,b,y;
ll xo[N],xe[N];
template<class T>
inline void read(T &x)
{
    x=0;ll f=1;static char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
    x*=f;
}

inline ll exgcd(ll a,ll b,ll &x,ll &y)
{
    ll ans,t;
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ans=exgcd(b,a%b,x,y);
    t=x;x=y;y=t-(a/b)*y;
    return ans;
}

inline ll check()
{
    memset(xe,0,sizeof(xe));
    xe[1]=xo[1];
    for(RT ll i=2;i<=2*n;i++)
    {
        xe[i]=(a*xe[i-1]+b)%mod;
        if((i&1)&&(xo[(i>>1)+1]!=xe[i]))
            return 0;
    }
    return 1;
}

int main()
{
    read(n);
    for(RT ll i=1;i<=n;i++)read(xo[i]);
    for(RT ll i=0;i<=10000;i++)
    {
        a=i;
        ll x3=xo[2],x1=xo[1],d=x3-a*a*x1;
        ll gcd=exgcd(a+1,mod,b,y);
        if(d%gcd)continue;
        b=b*d/gcd;
        if(check())break;
    }
    for(RT ll i=2;i<=2*n;i+=2)printf("%lld
",xe[i]);
    return 0;

}