【模线性方程】POJ 2115

2019-04-13 16:54发布

站内文章 / 模拟电子
11538 0 982
原文地址，感谢大神。 原文。
 题目链接
 题意：转化成c * x = b - a mod (2 ^ k)，解这个模线性方程的最小正整数解即可 
Sample Input 
3 3 2 16 
3 7 2 16 
7 3 2 16 
3 4 2 16 
0 0 0 0 

Sample Output 
0 
2 
32766 
FOREVER 

解方程：ax == b (mod n);【ax % n == b % n】 
设线性模方程的一个解为x0 
条件①：有d = gcd(a, n) 
条件②：有d = ax1 + ny, 由扩展欧几里得(Egcd)得到x1的值 
条件③：b % d == 0 (有解的条件) 
对条件③进行解释： 
原方程化为：ax + kn = b (设k为某一整数) 
那么如果a与n的最大公约数为d，那么ax + kn 必然可以提取一个d的因子，也就是说b必然有d这个因子，所以如果b%d!=0，说明b没有d这因子，与前面的结论相互矛盾，所以无解 

则x0 = x1*(b/d); 

证明： 
因为：容易求得d = gcd (a, n), 则存在一个x1、y使得d = ax1 + ny①(扩展欧几里得定理，这个都不会的话，说明你数论还没入门) 
方程①2边同时模n得：d % n == ax1 % n② 
又因为：b % d == 0, 即b是d的倍数; 
所以(b/d)必为整数; 
所以由②得： b % n == d*(b/d) % n == ax1*(b/d) % n == ax % n 
所以很容易可以看出x = x1*(b/d)是方程的一个整数解，得证 

参考文献：  #include #include #include //#include #include #include #include #include #include #include //#include #include using namespace std; #define LL long long #define inf 0x3fffffff LL Egcd (LL a, LL b, LL &x, LL &y) //扩展欧几里得 { if (b == 0) { x = 1, y = 0; return a; } LL d = Egcd (b, a%b, x, y); LL tp = x; x = y; y = tp - a/b*y; return d; } void MLE (LL a, LL b, LL n) //解模线性方程 { LL d, x, y; d = Egcd (a, n, x, y); if (b % d) { puts ("FOREVER"); return ; } LL x0 = x * (b/d); LL t = n / d; if (t < 0) t = -t; //以防万一，有的题目t有可能是负数 x0 = (x0 % t + t) % t; //防止负数出现，所以先模后加再模，再模是因为如果是正数，+n/d可能会超出n/d //对于无数个解形成的一群余数：周期个数是d，周期长度是n/d，也就是最小正整数解在n/d里，这个听老师说过，但是忘了为什么，涉及到群的概念…… printf ("%lld ", x0); } int main() { LL a, b, c, k; while (scanf ("%lld%lld%lld%lld", &a, &b, &c, &k), (a||b||c||k)) MLE (c, b-a, 1LL<

热门文章