POJ 2115 C Looooops 【线性模方程】 - c语言编程

TOP

POJ 2115 C Looooops 【线性模方程】

2014-11-23 22:13:10 来源: 作者: 【大中小】浏览:0次

题意：转化成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
#include
#include
#include
#include
//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：学习windows编程（8）--自己动手..	下一篇：扫雷外挂

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: