UVa 12169 (枚舉+擴展歐幾里得) Disgruntled Judge

題意：

給出四個數T, a, b, x₁,按公式生成序列 x_i = (a*x_i-1 + b) % 10001 (2 ≤ i ≤ 2T)

給出T和奇數項x_i，輸出偶數項x_i

分析：

最簡單的辦法就是直接枚舉a、b，看看與輸入是否相符。

 1 #include <cstdio>
 2 
 3 const int maxn = 10000 + 5;
 4 const int M = 10001;
 5 int T, x[maxn];
 6 
 7 int main()
 8 {
 9     //freopen("12169in.txt", "r", stdin);
10     
11     scanf("%d", &T);
12     for(int i = 1; i < 2*T; i += 2)
13         scanf("%d", &x[i]);
14     
15     bool ok;
16     for(int a = 0; a < M; ++a)
17     {
18         for(int b = 0; b < M; ++b)
19         {
20             ok = true;
21             for(int i = 2; i <= 2*T; i += 2)
22             {
23                 x[i] = (x[i-1]*a + b) % M;
24                 if(i < 2*T && x[i+1] != (x[i]*a + b) % M)
25                 {
26                     ok = false;
27                     break;
28                 }
29             }
30             if(ok) break;
31         }
32         if(ok) break;
33     }
34     
35     for(int i = 2; i <= 2*T; i += 2)
36         printf("%d\n", x[i]);
37     
38     return 0;
39 }

代碼君

第二種辦法枚舉a，根據x₁、x₃求b。

詳見這里

 1 #include <cstdio>
 2 
 3 typedef long long LL;
 4 const int maxn = 10000 + 5;
 5 const LL M = 10001;
 6 int T;
 7 LL x[maxn];
 8 
 9 void gcd(LL a, LL b, LL& d, LL& x, LL& y)
10 {
11     if(!b) { d = a; x = 1; y = 0; }
12     else { gcd(b, a%b, d, y, x); y -= x*(a/b); }
13 }
14 
15 int main()
16 {
17     //freopen("12169in.txt", "r", stdin);
18     
19     scanf("%d", &T);
20     for(int i = 1; i < 2*T; i += 2)
21         scanf("%lld", &x[i]);
22     
23     bool ok;
24     for(LL a = 0; a < M; ++a)
25     {
26         LL t = x[3] - a*a*x[1];
27         LL g, k, b;
28         gcd(a+1, M, g, b, k);
29         if(t % g != 0) continue;
30         b *= t / g;
31         
32         ok = true;
33         for(int i = 2; i <= 2*T; i += 2)
34         {
35             x[i] = (x[i-1]*a+b) % M;
36             if(i < 2*T && x[i+1] != (x[i]*a+b) % M)
37             {
38                 ok = false;
39                 break;
40             }
41         }
42         if(ok) break;
43     }
44     
45     for(int i = 2; i <= 2*T; i += 2)
46         printf("%lld\n", x[i]);
47     
48     return 0;
49 }

代碼君

轉載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4162183.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/375432.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/375432.shtml
英文地址，請注明出處：http://en.pswp.cn/news/375432.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！