題目大意：

對于 f[i] = (f[i-1]*a + b) mod 10001，已知f[1],f[3]……f[n*2-1]，求f[2],f[4]……f[n*2]

題目思路：

很明顯，我們需要計算a,b的值。很容易得到：(a+1)*b + 10001*(-k) = f[3]-a*a*f[1]

利用擴展歐幾里得計算：(a+1)*b0 + 10001*(-k0) = gcd(a+1,10001)

聯立方程有：b = b0*(f[3]-a*a*f[1])/gcd(a+1,10001)

將b帶入f[]，驗證是否成立即可

//#pragma GCC optimize(2) #include<stdio.h> #include<algorithm> #include<string.h> #include<stdlib.h> #include<iostream> #include<stack> #include<vector> #include<math.h> using namespace std; #define LL long long #define INF 0x3f3f3f3fLL p[205];bool Judge(LL a,LL b,LL T) {LL pre = p[1];LL now;for(int i=2;i<=2*T;i++){now = (pre*a + b) % 10001;if(i&1 && now != p[i])return false;pre = now;}return true; }void Exgcd(LL a,LL b,LL &gcd,LL &x,LL &y) {if(!b){gcd = a;x = 1;y = 0;}else{Exgcd(b,a%b,gcd,y,x);y -= x*(a/b);} }int main() {LL T;while(cin >> T){for(int i=1;i<=2*T;i+=2)cin >> p[i];for(int a=0;;a++){LL k,b,gcd,c=p[3]-a*a*p[1];Exgcd(a+1,10001,gcd,b,k);if(c%gcd !=0 ) continue;LL temp = c/gcd;b *= temp;if(Judge(a,b,T)){for(int i=2;i<=2*T;i+=2)cout << (a*p[i-1]+b)%10001 << endl;break;}}}return 0; } View Code

?

轉載于:https://www.cnblogs.com/alan-W/p/10803178.html

總結

以上是生活随笔為你收集整理的Disgruntled Judge UVA - 12169的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。