首页 > 代码库 > UVa12169 Disgruntled Judge

UVa12169 Disgruntled Judge

2024-08-14 09:17:08   218人阅读

 

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


联系
我们