http://poj.org/problem?id=2115
题意:转化成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 <iostream>
#include <algorithm>
#include <string>
//#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
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\n", 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<<k);
return 0;
}
- 大小: 64.5 KB
分享到:
相关推荐
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
POJ水题集-----50道左右-----增加自信啊..
poj 1690 Your-Term-Project.md
ACM-POJ2115-C Looooops 测试数据。 数据来源:CTU Open 2004 问题C
poj 1240 Pre-Post-erous!.md
西北工业大学-c语言-POJ-题目及答案-第七季.doc
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
用Java代码实现POJ(PKU)上题2494!
很有用的解题报告。。是acm初级提高的必备资料。。。。。
poj 1028 Web Navigation 的代码,已通过!
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
非常全的poj答案库 1164-1874 1000-4007
北大POJ2299-Ultra-QuickSort 解题报告+AC代码
POJ3211--Washing Clothes
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
poj题目分类--acmer做题极有用资源
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类