首页 > 程序开发 > 软件开发 > C语言 >

POJ 2115 C Looooops 【线性模方程】

2011-06-26

题意:转化成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】 设线性

题意:转化成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 (有解的条件)
则x0 = x1*(b/d);

证明:
因为:容易求得d = gcd (a, n), 则有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)是方程的一个整数解,得证

参考文献:

C++代码
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define L long long

L Egcd (L a, L b, L &x, L &y) //扩展欧几里得
{
L d, tp;
if (b == 0)
{
x = 1, y = 0;
return a;
}
d = Egcd (b, a%b, x, y);
tp = x;
x = y;
y = tp - (a/b)*y;
return d;
}
void MLE (L a, L b, L n) //解模线性方程
{
L x, y, d;
d = Egcd (a, n, x, y);
if (b % d == 0)
{
L x0 = (b / d * x) % n + n;
cout << x0 % (n/d) << endl;
//对于无数个解形成的一群余数:周期个数是d,周期长度是n/d,也就是最小正整数解在n/d里,这个听老师说过,但是忘了为什么,涉及到群的概念……
}
else puts ("FOREVER"); //无解
}
int main()
{
L a, b, c;
int k;
while (cin >> a >> b >> c >> k)
{
if (!a && !b && !c && !k)
break;
MLE (c, b - a, 1LL << k);
}
return 0;
}

相关文章
最新文章
热点推荐