首页 > 代码库 > UVA 12169 Disgruntled Judge 枚举+扩展欧几里得
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;}
UVA 12169 Disgruntled Judge 枚举+扩展欧几里得
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。