首页 > 代码库 > UVa12169 Disgruntled Judge
UVa12169 Disgruntled Judge
x2 = (a * x1 + b) % 10001;
x3 = (a * x2 + b) % 10001;
∴x3 = (a * (a * x1 + b) % 10001 + b ) % 10001;
∴(a + 1) * b + 10001 * (-k) = x3 - a * a * x1
由于a的范围是1~10000,所以可以枚举a,解出b,暴力判断这组a和b能否适用于所有的x
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 const int mod=10001;10 const int mxn=50000;11 LL num[mxn];12 LL x[mxn];13 LL k,b;14 int n;15 LL exgcd(LL a,LL b,LL &x,LL &y){16 if(!b){17 x=1;y=0;18 return a;19 }20 LL tmp=exgcd(b,a%b,x,y);21 LL t=x;x=y;y=t-a/b*y;22 return tmp;23 }24 int main(){25 scanf("%d",&n);26 int i,j;27 for(i=1;i<=n;i++){28 scanf("%lld",&num[i]);29 }30 for(int a=0;a<mod;a++){31 LL tmp=num[2]-a*a*num[1];32 LL gcd=exgcd(a+1,mod,k,b);33 if(tmp%gcd)continue;34 // printf("test:%lld\n",tmp);35 b=k*tmp/gcd%mod;36 bool ok=1;37 x[1]=(num[1]*a+b)%mod;38 for(i=2;i<=n;i++){39 if(num[i]!=(x[i-1]*a+b)%mod){40 ok=0;41 break;42 }43 x[i]=(num[i]*a+b)%mod;44 }45 if(!ok)continue;46 //if ok47 for(i=1;i<=n;i++)printf("%lld\n",x[i]);48 break;49 }50 return 0;51 }
UVa12169 Disgruntled Judge
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。