首页 > 代码库 > UVa 12169 (枚举+扩展欧几里得) Disgruntled Judge
UVa 12169 (枚举+扩展欧几里得) Disgruntled Judge
题意：
给出四个数T, a, b, x1,按公式生成序列 xi = (a*xi-1 + b) % 10001 (2 ≤ i ≤ 2T)
给出T和奇数项xi，输出偶数项xi
分析：
最简单的办法就是直接枚举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，根据x1、x3求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 }
UVa 12169 (枚举+扩展欧几里得) Disgruntled Judge
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。