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
分享到:
相关推荐
- **例题**:poj2635, poj3292, poj1845, poj2115 - **解释**:排列组合问题通常涉及从n个不同元素中选取k个元素的所有可能的方式。 #### 3. 概率统计 - **例题**:poj3273, poj3258, poj1905, poj3122 - **解释**...
4. **数学知识**:题目可能涉及到线性代数、组合数学、数论等数学概念,例如求解线性方程组或处理组合优化问题。 5. **字符串处理**:如果"Eqs"与字符串处理有关,那么可能涉及到字符串匹配、模式查找等操作。 6. ...
- **示例题目**: poj2635, poj3292, poj1845, poj2115 - **知识点**: - **素数判定**:判断一个数是否为素数。 - **欧拉函数**:小于等于n的正整数中与n互质的数的个数。 #### 3. 几何问题 - **内容**: 包括计算...
【标题】"POJ1716-Integer Intervals【Difference Constraints】" 是一个编程竞赛题目,来源于北京大学的在线评测系统POJ(Problem Online Judge)。这个题目主要涉及到差分约束系统(Difference Constraints)的...
3. **数值求解**:如线性方程组的求解(poj2187, poj1113)。 ### 十、C++模板和库 1. **C++标准模板库**:如STL的使用技巧(poj3096, poj3007)。 2. **自定义数据结构**:创建和使用自定义的数据结构和算法(poj...
- **模线性方程**:这个问题实质上转化为求解模线性方程 (m - n)t = (x - y) mod L 的最小正整数解 t 的问题。 - **求解方法**:求解模线性方程 ax = b (mod n) 的方法如下: - 首先计算 a 和 n 的最大公约数 d =...
在编程竞赛中,例如 POJ 1061、2115 和 2142 题目,常常会用到一元线性同余方程的解法。 当涉及到一元线性同余方程组时,可以采用两两合并的方式来求解。通过计算每两个方程的解,可以找到整个方程组的解。例如,在...
【北大POJ初级-基本算法】是一系列针对北京大学在线编程平台POJ的初级算法题目解题报告和通过(AC)代码的集合。这个资源对于学习算法基础和提升编程能力非常有帮助,尤其适合初学者。POJ是许多计算机科学与技术专业...
- POJ 2115: 概率统计的复杂案例 - **组合几何**:涉及组合数学与几何学的结合。 - **示例题目**: - POJ 3273: 组合几何的基础应用 - POJ 3258: 组合几何的高级用法 - POJ 1905: 组合几何的变种问题 - POJ ...
4. **数论**:包括素数检测(质数筛法)、最大公约数(辗转相除法、欧几里得算法)和最小公倍数等,以及模运算的性质,如模线性同余方程的解法。 5. **图论基础**:虽然初级阶段可能不会深入,但图的基本概念如路径...
中国剩余定理(Chinese Remainder Theorem,CRT)是数论中的一个重要结果,它解决了以下一类模线性同余方程组的问题: x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ an (mod mn) 其中,a1, a2, ..., an 和 m1, m2,...
- **鸡兔同笼**(2.1 例题):这是一个经典的数学问题,涉及到线性方程组的求解,可以使用穷举、递推或高斯消元等方法。 - **棋盘上的距离**(2.2 例题):可能涉及到平面几何计算,计算两点之间的欧几里得距离或...
3. **数学知识**:组合数学、数论(模运算、同余方程、最大公约数与最小公倍数、质因数分解等)、概率统计、线性代数、数列(斐波那契数列、等差数列、等比数列等)。 4. **字符串处理**:KMP算法、Boyer-Moore算法...
这个问题可以通过解决一个单变元模线性方程来解答,即`Cx = (B - A) (mod 2^k)`。这里的`C`、`B - A`和`2^k`分别被记为`a`、`b`和`n`,从而形成标准模线性方程`ax = b (mod n)`。解这个问题的关键是找到最大公约数`d...
4. **数学**:数论(最大公约数、最小公倍数、质因数分解、模运算等)、组合数学(排列组合、鸽巢原理等)、线性代数、概率论等。 5. **其他**:位操作、编码解码、模拟、图论问题(最短路径、最小生成树、网络流等...
例如,POJ-2115C可能是一个关于循环计数或者循环结构的题目,而POJ-1061青蛙的约会可能涉及到跳跃和相遇的概率计算,这些场景都可能需要用到模逆元,而求模逆元恰好是拓展欧几里德算法的一个应用。 模逆元在模运算...
5. **向量和矩阵**:向量的加减乘运算、标量积和向量积,矩阵的乘法,以及它们在几何中的应用,如求解线性方程组。 6. **旋转和平移**:在二维或三维空间中,物体的旋转和平移可以通过坐标变换实现,这在图形学中尤...
- 解模线性方程:求解形如\(ax \equiv b \pmod{m}\)的方程。这类问题通常出现在密码学中。 6. **计算几何** - 凸壳:找到一组点的凸包,即这些点构成的最小凸多边形。常见的算法包括Graham扫描法和Jarvis步进法。 ...
3.2 模线性方程组 108 3.3 素数 110 3.4 欧拉函数 114 3.6高精度 116 3.6.1平方根 116 3.6.2 高精度乘幂 117 3.7 高斯消元回代法 122 3.8 数值计算 124 3.8.1 定积分计算 124 3.8.2 多项式求根(牛顿法) 125 3.8.3 ...