当前位置：首页 > news >正文

UVA - 12169 Disgruntled Judge（枚举+扩展欧几里得）

news 来源：原创 2024/5/4 3:31:01

题目链接

这道题一开始并不知道怎么做，尽管想到了枚举，但是枚举的时间复杂度为 $O(t*n^2)$ ，然后就没多想了（但是UVA牛掰的评测机似乎可以跑过）

看LRJ的分析是，想办法得到 $a$ ，然后再计算出 $b$ 。不难想到可以枚举 $a$ ，但是表达式中的取模似乎很难解决，然后就卡住了…

实际上是我太年轻，这点东西都没想到：已知 $x_3=[a((ax_1+b)\%10001)+b]\%10001$ ，化简过程中所有的模 $10001$ 替换成一个未知项 $10001 * (- k)$ ，即：

$x_3=a^2x_1+(a+1)*b+10001*(-k)$ ， $x_3,x_1,a$ 已知，那么移项可得：

$a+1)*b+10001*(-k)=x_3-a^2x_1$

当然此方程式有解的充要条件为： $x_3-a^2x_1)\%gcd(a+1,10001)==0$ ，那么我们用扩欧解方程式 $(a + 1) * b + 10001 * (- k) = g c d (a + 1, 10001)$ 即可

时间复杂度 $O (n * t * l o g n)$

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=10001;

int t;
ll x[210];

ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}

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

bool check(ll a,ll b){
    for(int i=1;i<=2*t;i++){
        if(i&1){
            if(i>1){
                ll res=(a*x[i-1]+b)%maxn;
                if(res!=x[i]) return false;
            }
        }else{
            x[i]=(a*x[i-1]+b)%maxn;
        }
    }
    return true;
}

void print(){
    for(int i=2;i<=2*t;i+=2)
        printf("%lld\n",x[i]);
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int a,b;
    scanf("%d",&t);
    for(int i=1;i<=2*t;i+=2)
        scanf("%d",&x[i]);
    for(int i=0;i<maxn;i++){
        ll c=x[3]-i*i*x[1],a=i+1,b=maxn;
        ll g=gcd(a,b);
        if(c%g==0){
            ll x,y;
            exgcd(a,b,x,y);
            ll p=c/g;
            x*=p;
            if(check(i,x)){
                print();
                return 0;
            }
        }
    }
    return 0;
}