uva12169（模算数）

2019-04-13 14:48发布

站内文章 / 模拟电子
12978 0 1618
题目大意： 现在一个裁判找了三个数x1,a,b,他根据x[i]=(a*x[i-1]+b)mod10001,计算出了一个长度为2*T的数列。现在给出T和x[1],x[3]...x[2*T-1],现在要你输出x[2],x[4]...x[2*T],如果有多组输出，输出任意一组即可。
题目分析： 如果知道了a，就可以计算出x2，进而利用扩展欧几里得算出b。有了x1，a，b，就可以得出所求序列。因为扩展欧几里得只能解两个未知数的方程，所以我通过枚举a，来求得满足条件的a，b值。
代码： #include #include #include using namespace std; typedef long long LL; const LL maxn=20000; const LL mod=10001; LL T,n; LL x[maxn]; void extend_gcd(LL a,LL b,LL& d,LL& x,LL& y) { if(!b){ d=a;x=1;y=0; } else{ extend_gcd(b,a%b,d,y,x); y-=x*(a/b); } } void print() { for(int i=2;i<=2*n;i+=2){ cout<>n) { for(LL i=1;i<=2*n;i+=2){ cin>>x[i]; } for(LL a=0;a<=10000;a++){ LL val=x[3]-a*a*x[1]; LL b,d,k; extend_gcd(a+1,mod,d,b,k); if(val%d) continue; b=b*val/d; if(judge(a,b)){ print(); break; } } } return 0; }

热门文章