`

【模线性方程】POJ 2115 【更新日期2011-11-18】

阅读更多
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
11
7
分享到:
评论

相关推荐

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj2635, poj3292, poj1845, poj2115 - **解释**:排列组合问题通常涉及从n个不同元素中选取k个元素的所有可能的方式。 #### 3. 概率统计 - **例题**:poj3273, poj3258, poj1905, poj3122 - **解释**...

    POJ1840-Eqs

    4. **数学知识**:题目可能涉及到线性代数、组合数学、数论等数学概念,例如求解线性方程组或处理组合优化问题。 5. **字符串处理**:如果"Eqs"与字符串处理有关,那么可能涉及到字符串匹配、模式查找等操作。 6. ...

    POJ题目分类

    - **示例题目**: poj2635, poj3292, poj1845, poj2115 - **知识点**: - **素数判定**:判断一个数是否为素数。 - **欧拉函数**:小于等于n的正整数中与n互质的数的个数。 #### 3. 几何问题 - **内容**: 包括计算...

    POJ1716-Integer Intervals【Difference Constraints】

    【标题】"POJ1716-Integer Intervals【Difference Constraints】" 是一个编程竞赛题目,来源于北京大学的在线评测系统POJ(Problem Online Judge)。这个题目主要涉及到差分约束系统(Difference Constraints)的...

    ACM-POJ 算法训练指南

    3. **数值求解**:如线性方程组的求解(poj2187, poj1113)。 ### 十、C++模板和库 1. **C++标准模板库**:如STL的使用技巧(poj3096, poj3007)。 2. **自定义数据结构**:创建和使用自定义的数据结构和算法(poj...

    poj 1061 解题报告 有源码

    - **模线性方程**:这个问题实质上转化为求解模线性方程 (m - n)t = (x - y) mod L 的最小正整数解 t 的问题。 - **求解方法**:求解模线性方程 ax = b (mod n) 的方法如下: - 首先计算 a 和 n 的最大公约数 d =...

    人工智能基础-线性同余方程.pdf

    在编程竞赛中,例如 POJ 1061、2115 和 2142 题目,常常会用到一元线性同余方程的解法。 当涉及到一元线性同余方程组时,可以采用两两合并的方式来求解。通过计算每两个方程的解,可以找到整个方程组的解。例如,在...

    北大POJ初级-基本算法

    【北大POJ初级-基本算法】是一系列针对北京大学在线编程平台POJ的初级算法题目解题报告和通过(AC)代码的集合。这个资源对于学习算法基础和提升编程能力非常有帮助,尤其适合初学者。POJ是许多计算机科学与技术专业...

    acm新手训练方案新手必备

    - POJ 2115: 概率统计的复杂案例 - **组合几何**:涉及组合数学与几何学的结合。 - **示例题目**: - POJ 3273: 组合几何的基础应用 - POJ 3258: 组合几何的高级用法 - POJ 1905: 组合几何的变种问题 - POJ ...

    北大POJ初级-数学

    4. **数论**:包括素数检测(质数筛法)、最大公约数(辗转相除法、欧几里得算法)和最小公倍数等,以及模运算的性质,如模线性同余方程的解法。 5. **图论基础**:虽然初级阶段可能不会深入,但图的基本概念如路径...

    POJ1006-Biorhythms【中国剩余定理】

    中国剩余定理(Chinese Remainder Theorem,CRT)是数论中的一个重要结果,它解决了以下一类模线性同余方程组的问题: x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ an (mod mn) 其中,a1, a2, ..., an 和 m1, m2,...

    初学者练题开始------在POJ上(注:是百练)

    - **鸡兔同笼**(2.1 例题):这是一个经典的数学问题,涉及到线性方程组的求解,可以使用穷举、递推或高斯消元等方法。 - **棋盘上的距离**(2.2 例题):可能涉及到平面几何计算,计算两点之间的欧几里得距离或...

    poj大量习题详解ACM

    3. **数学知识**:组合数学、数论(模运算、同余方程、最大公约数与最小公倍数、质因数分解等)、概率统计、线性代数、数列(斐波那契数列、等差数列、等比数列等)。 4. **字符串处理**:KMP算法、Boyer-Moore算法...

    模同余与公约数题解1

    这个问题可以通过解决一个单变元模线性方程来解答,即`Cx = (B - A) (mod 2^k)`。这里的`C`、`B - A`和`2^k`分别被记为`a`、`b`和`n`,从而形成标准模线性方程`ax = b (mod n)`。解这个问题的关键是找到最大公约数`d...

    POJ1000-1299中的80题AC代码

    4. **数学**:数论(最大公约数、最小公倍数、质因数分解、模运算等)、组合数学(排列组合、鸽巢原理等)、线性代数、概率论等。 5. **其他**:位操作、编码解码、模拟、图论问题(最短路径、最小生成树、网络流等...

    extend_gcd.zip_欧几里德联合

    例如,POJ-2115C可能是一个关于循环计数或者循环结构的题目,而POJ-1061青蛙的约会可能涉及到跳跃和相遇的概率计算,这些场景都可能需要用到模逆元,而求模逆元恰好是拓展欧几里德算法的一个应用。 模逆元在模运算...

    北大POJ初级-计算几何学

    5. **向量和矩阵**:向量的加减乘运算、标量积和向量积,矩阵的乘法,以及它们在几何中的应用,如求解线性方程组。 6. **旋转和平移**:在二维或三维空间中,物体的旋转和平移可以通过坐标变换实现,这在图形学中尤...

    pojacm题目具体分类

    - 解模线性方程:求解形如\(ax \equiv b \pmod{m}\)的方程。这类问题通常出现在密码学中。 6. **计算几何** - 凸壳:找到一组点的凸包,即这些点构成的最小凸多边形。常见的算法包括Graham扫描法和Jarvis步进法。 ...

    浙江大学ACM模板 计算几何,图论,数据结构,经典题的模板

    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 ...

Global site tag (gtag.js) - Google Analytics