POJ 2891 扩展欧几里德
这个题乍一看跟剩余定理似的,但是它不满足两两互素的条件,所以不能用剩余定理,也是给了一组同余方程,找出一个X满足这些方程,如果找不到的话就输出-1
因为它不满足互素的条件,所以两个两个的合并,最后合成一个。
题目给定的是
M % m1 = r1
M % m2 = r2
......
M % mn = rn
只需将两个式子合并成一个式子,那么这个合并的这个式子就可以继续和下面的式子继续合并,知道合到最后一个式子。
首先来看下两个式子怎么合并。
M % m1 = r1 可以写成 M = k1 * m1 + r1;
同理M = k2 * m2 + r2
所以k1 * m1 + r1 = k2 * m2 + r2
k1 * m1 - k2 * m2 = r2 - r1
将k1 看成x, m1看成a, k2看成y, m2看成b, r2 - r1看成c
那么这个式子就变成了
ax-by=c;不定方程
这时候就可以用不定方程来解了。
因为题目给的两两可能不互素,所以gcd(a, b) 有可能不等于1,所以,这个方程不一定有解,所以就是判断这个题有没有解的条件。
如果有解的话,用扩展欧几里德可以的出这个方程的解,然后将x带入到 k1 * m1 + r1中得到M,这时候M就是这两个方程组的一个特解,通解就是M' = M + K * LCM(m1, m2);
这个式子可以变化成M' % LCM(m1, m2) = M;所以又可以继续跟下面的式子合并了。所以这个式子对应的余数r就是M, 模数(就是式子中的mi)就是LCM(m1,m2);
到这里之后就合并好了一个式子。下面就是继续按照这个过程合并到第n个式子了。最后合并完之后就剩下一个式子,求出来的M就是方程组的特解,通解为M' = M + k * LCM; 其中LCM = LCM(m1, m2...mn), 最小正整数解为(M % LCM + LCM) % LCM;
还有一个坑就是如果边输入边处理的话,不要找到无解立马就跳出循环,因为后面的数据还没输入完。
代码如下:
/*************************************************************************
> File Name: 5.cpp
> Author: Howe Young
> Mail: 1013410795@qq.com
> Created Time: 2015年08月01日 星期六 15时39分47秒
************************************************************************/ #include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + ;
typedef long long ll;
ll m[maxn], r[maxn];
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (b == )
{
x = ;
y = ;
return a;
}
ll r = exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - a / b * y;
return r;
}
int main()
{
int k;
while (~scanf("%d", &k))
{
for (int i = ; i <= k; i++)
scanf("%lld %lld", &m[i], &r[i]);
ll m1, m2, r1, r2, c, d;
m1 = m[]; r1 = r[];
bool flag = true;
for (int i = ; i <= k; i++)
{
ll x, y;
d = exgcd(m1, m[i], x, y);
if ((r[i] - r1) % d != )
{
flag = false;
break;
}
c = r[i] - r1;
x = c / d * x % (m[i] / d);
r1 = m1 * x + r1;
m1 = m1 / d * m[i];
r1 %= m1;
}
if (!flag)
{
printf("-1\n");
continue;
}
r1 = (r1 + m1) % m1;
printf("%lld\n", r1);
} return ;
}
最新文章
- BPM公文管理解决方案分享
- 字符串的replace()方法隐藏着什么不可告人秘密?
- php框架laravel:数据库建立:artisan
- 加强型无穷集合:InfiniteList<;T>;,可指定遍历方向和偏移量,只要集合有元素并且偏移量不为 0,将永远遍历下去。
- Javascript笔记一
- 深入解析DC/OS 1.8 – 高可靠的微服务及大数据管理平台
- python 重载 __hash__ __eq__
- 《第一行代码》学习笔记20-广播接收器Broadcast_Receiver(3)
- NSIndexPath 延伸
- 动态添加试题选项按钮 radioButton(一)
- HTML,CSS,JS之间的关系
- docker修改容器参数
- pyqt多线程进度条
- 关于visual studio的一些日常总结
- DotNetBar的窗口样式丢失
- SpringMVC+jquery.uploadify 上传文件
- CONFIG_DEBUG_USER【转】
- Cdq分治整体二分学习记录
- 【转】字符编码笔记:ASCII,Unicode 和 UTF-8
- go语言中make和new的区别
热门文章
- Js冒泡事件和捕获事件
- B题 - A+B for Input-Output Practice (I)
- Java中的那些名词术语(不断更新中)
- 理解Java机制最受欢迎的8幅图
- android 如何进入某个具体的应用管理页面
- 疯狂java讲义笔记 2.3.7
- UVA 10706 Number Sequence (找规律 + 打表 + 查找)
- 数据结构:HDU 2993 MAX Average Problem
- Selenium自动化测试环境搭建汇总(一):Selenium+Eclipse+Junit+TestNG
- 使用vs2010编译 Python \ SIP \ PyQt4