「算法笔记」CRT 与 exCRT
一、扩展欧几里得
求解方程 \(ax+by=\gcd(a,b)\)。
int exgcd(int a,int b,int &x,int &y){
if(!b) return x=1,y=0,a;
int d=exgcd(b,a%b,x,y);
int z=x; x=y,y=z-y*(a/b);
return d;
}
对于更为一般的方程 \(ax+by=c\),设 \(d=\gcd(a,b)\)。我们可以求出 \(ax+by=d\) 的一组特解 \(x_0,y_0\)。这所以 \(\frac{c}{d}\) 也必须为整数,否则无解(所以该方程有解当且仅当 \(d\mid c\))。我们令 \(x_0,y_0\) 同时乘上 \(\frac{c}{d}\),得 \(a\frac{cx_0}{d}+b\frac{cy_0}{d}=c\)。那么 \(x=\frac{c}{d}\cdot x_0,y=\frac{c}{d}\cdot y_0\) 即为一组解。
事实上,方程 \(ax+by=c\) 的通解可以表示为:
那么若求得一个 \(x\),则该方程 \(x\) 的最小整数解就是 (x%(b/d)+b/d)%(b/d)
。
二、中国剩余定理
1. 求解
考虑求解方程组 \(x\equiv r_i\pmod {m_i}\)。即:
其中 \(m_i\) 两两互质。中国剩余定理(CRT)的表述如下:
令 \(M=\prod_{i=1}^k m_i\),则该方程组在 \([0,M)\) 范围内有唯一解,且显然是最小整数解。设 \(M_i=\frac{M}{m_i}\),\(t_i=M_i^{-1}\) 表示 \(M_i\) 在模 \(m_i\) 意义下的逆元,即 \(M_it_i\equiv 1\pmod {m_i}\)。则最小解为:
2. 证明
当 \(i\neq j\) 时,\(M_i=\frac{m_1m_2\cdots m_k}{m_i}\) 必为 \(m_j\) 的倍数,则有 \(r_it_iM_i\equiv 0\pmod {m_j}\)。
否则,又因为 \(M_jt_j\equiv 1\pmod {m_i}\),所以 \(r_jt_jM_j\equiv r_j\pmod {m_j}\)。
综上,对于任意 \(i\),总有 \(x=\sum_{i=1}^k r_it_iM_i\equiv r_i\pmod {m_i}\)。
三、扩展中国剩余定理
考虑 \(m_i\) 不互质的情况。
设当前求解到第 \(i\) 个方程,前 \(i-1\) 个方程的最小解为 \(X\),\(\text{lcm}(m_1,m_2,\cdots,m_{i-1})=M\)。则前 \(i-1\) 个方程的通解为 \(X+tM\)(\(t\) 为任意非负整数)。
考虑第 \(i\) 个方程,现在要找一个 \(t\),使得 \(X+tM\equiv r_i\pmod {m_i}\)。
移项得:\(tM\equiv r_i-X\pmod {m_i}\)。进一步转化为:\(tM+pm_i=r_i-X\)。显然这是一个不定方程,可以用 exgcd 求解。
解出最小的 \(t\) 后,更新 \(X=X+tM\),\(M=\text{lcm}(M,m_i)\)。
最后为保证 \(X\) 最小,还需对 \(M\) 取模。
//Luogu P4777
#include<bits/stdc++.h>
#define int long long
#define LLL __int128 //过程中某个地方会炸。或改用快速乘。
using namespace std;
const int N=1e5+5;
int n,m[N],r[N],M;
int exgcd(int a,int b,int &x,int &y){
if(!b) return x=1,y=0,a;
int d=exgcd(b,a%b,x,y);
int z=x; x=y,y=z-y*(a/b);
return d;
}
int exCRT(int n){
int M=m[1],X=r[1];
for(int i=2;i<=n;i++){
int a=M,b=m[i],c=r[i]-X,x,y,d=exgcd(a,b,x,y),t;
if(c%d) return -1;
a/=d,b/=d,c/=d,t=((LLL)x*c%b+b)%b;
X+=t*M,M*=m[i]/d,X=(X+M)%M;
}
return X;
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&m[i],&r[i]);
printf("%lld\n",exCRT(n));
return 0;
}
最新文章
- Scala - 隐式转换和隐式参数
- 车销宝无线开单PDA 一款互联网+POS神器 无缝与电脑数据同步 无线POS开单解决方案
- Spring学习记录(三)---bean自动装配autowire
- jquery 时间戳与日期转换
- 循序渐进Python3(十)-- 4 -- paramiko
- 工程BUG记录
- [Qt5] Develop openCV3 by QML on Qt-creator
- java中的字符,字符串,数字之间的转换
- Java 命令行运行参数大全
- LUA OOP 单例模式实现的 一个 方案
- ajax页面排序的序号问题
- SliverLight(how to show data point on the column series)
- [Linked List]Partition List
- 循环结构中break、continue、return和exit的区别
- 大数据系列修炼-Scala课程06
- kairosdb + cassandra Setup
- Docker 镜像之进阶篇
- (转)RBAC权限管理
- [python,2018-06-25] 高德纳箭号表示法
- vscode中iview的<;/Col>;标签报错问题
热门文章
- React 16.13.1触发两次render
- 转 【Android】- Android与html5交互操作
- Insert into select语句引发的生产事故
- 记录一下使用MySQL的left join时,遇到的坑
- Output of C++ Program | Set 4
- spring 事务处理中,同一个类中:A方法(无事务)调B方法(有事务),事务不生效问题
- Spring支持5种类型的增强
- Ajax请求($.ajax()为例)中data属性传参数的形式
- 【Github】如何下载csv文件/win10如何修改txt文件为csv文件
- Mysql脚本 生成测试数据