UVa 12169 - Disgruntled Judge(扩展欧几里得+枚举) 发表于 2015-07-27 | 分类于 AOAPC II , Chapter 10. Maths | 首先枚举所有 a ,然后利用扩展欧几里得算法求出 b 。之后进行验证。1234567891011121314151617181920212223242526272829303132333435#include<cstdio>typedef long long LL;using namespace std;const int maxn=210;LL x[maxn];void exgcd(LL a,LL b,LL& d,LL& x,LL& y){ if(!b) d=a,x=1,y=0; else exgcd(b,a%b,d,y,x),y-=x*(a/b);}int main(){ int t;scanf("%d",&t); for(int i=0;i<t;++i) scanf("%lld",&x[2*i]); t<<=1; for(LL a=0;;++a){ LL k,b,d,tmp=x[2]-a*a*x[0]; exgcd(10001,a+1,d,k,b); if(tmp%d) continue; b=b*tmp/d; bool flag=true; for(int i=1;i<t;++i){ if(i&1) x[i]=(a*x[i-1]+b)%10001; else { if(x[i]!=(a*x[i-1]+b)%10001){ flag=false; break; } } } if(flag) break; } t>>=1; for(int i=0;i<t;++i) printf("%lld\n",x[2*i+1]); return 0;}本文迁移自我的 CSDN博客 ,格式可能有所偏差。