当前位置:网站首页>扩展中国剩余定理
扩展中国剩余定理
2022-08-10 20:54:00 【aWty_】
exCRT
CRT
关于 C R T CRT CRT,主要的思想是这样的,对于一个方程组:
{ x ≡ a 1 ( m o d m 1 ) x ≡ a 1 ( m o d m 2 ) ⋮ x ≡ a n ( m o d m n ) \begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_1 \pmod {m_2} \\ \vdots \\ x \equiv a_n \pmod {m_n} \end{cases} ⎩⎨⎧x≡a1(modm1)x≡a1(modm2)⋮x≡an(modmn)
来说我们令:
m = ∏ i = 1 n m i , M i = m m i m = \prod_{i = 1}^n m_i, M_i = \frac m {m_i} m=i=1∏nmi,Mi=mim
然后求出 M i M_i Mi 在模 m i m_i mi 意义下的乘法逆元 t i t_i ti,于是我们就得到了答案:
a n s = ∑ i = 1 n a i M i t i ans = \sum_{i = 1}^n a_i M_i t_i ans=i=1∑naiMiti
在这里的计算步骤中,显然在计算逆元的时候要求 gcd ( M i , m i ) = 1 \gcd(M_i, m_i) = 1 gcd(Mi,mi)=1,那么也就是要求 { m i } \{ m_i \} { mi} l两两互质。
exCRT
总体思路
扩展中国剩余定理就是要解决 m i m_i mi 两两不互质的情况时解方程的方法。
但是我们稍微经过一些思考就能发现,要想在 C R T CRT CRT 的基础上小改一下来实现 e x C R T exCRT exCRT 时不可能的,因为如果 gcd ( M i , m i ) ≠ 1 \gcd(M_i, m_i) \neq 1 gcd(Mi,mi)=1 的话那么连逆元都不存在了,所以我们需要跳出 C R T CRT CRT 的框架来思考怎样进行扩展。
我们考虑合并两个方程,如果可以做到很快的合并,那么我们只需要一直合并下去再直接求解剩下的,唯一一个的,简单的,显然的,线性同余方程就能解决问题了。
合并
考虑两个方程的合并:
{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) \begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \end{cases} { x≡a1(modm1)x≡a2(modm2)
那么根据同余的性质我们就能得到:
x = k 1 m 1 + a 1 = k 2 m 2 + a 2 x = k_1m_1 + a_1 = k_2 m_2 + a_2 x=k1m1+a1=k2m2+a2
移一下项:
k 1 m 1 − k 2 m 2 = a 2 − a 1 k_1m_1 - k_2m_2 = a_2 - a_1 k1m1−k2m2=a2−a1
这个式子的形式可能没有那么直观,所以我们令 a = m 1 , b = m 2 , c = a 2 − a 1 , x = k 1 , y = − k 2 a = m_1, b = m_2, c = a_2 - a_1, x = k_1, y = -k_2 a=m1,b=m2,c=a2−a1,x=k1,y=−k2,这个式子是不是就瞬间变成了这样:
a x + b y = c ax + by = c ax+by=c
这就是一个经典的不定方程求解的问题了,那么根据裴蜀定理,我们就能知道:
- 如果 gcd ( m 1 , m 2 ) ∣ ( r 2 − r 1 ) \gcd(m_1, m_2) \mid (r_2 - r_1) gcd(m1,m2)∣(r2−r1),那么方程可以直接用 e x g c d exgcd exgcd 求出她的一组特殊解
- 否则,方程无解
那么我们求出 x = k 1 m 1 + a 1 x = k_1m_1 + a_1 x=k1m1+a1 之后就得到了一个 x x x 的特殊解同时满足这两个方程。我们给这个特殊解一个新的变量名 X X X。
于是我们就可以愉快的构造新的方程了:
x ≡ X ( m o d l c m ( m 1 , m 2 ) ) x \equiv X \pmod {lcm(m_1, m_2)} x≡X(modlcm(m1,m2))
这个构造应该是非常显然的,因为 x x x 与 X X X 模 m 1 m_1 m1 同余且 x x x 与 X X X 模 m 2 m_2 m2 同余,那么 x x x 与 X X X 模 l c m ( m 1 , m 2 ) lcm(m_1, m_2) lcm(m1,m2) 同余。
算法流程总结
- 在所有方程中取两个出来
- 合并(如果不能合并输出无解)
- 只剩下一个方程直接解这唯一的一个方程得到答案
完结撒花!!!
代码
#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define in read()
#define MAXN 100100
inline int read(){
int x = 0; char c = getchar();
while(c < '0' or c > '9') c = getchar();
while('0' <= c and c <= '9'){
x = x * 10 + c - '0'; c = getchar();
}
return x;
}
void write(int x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int n = 0;
int a[MAXN] = {
0 };
int m[MAXN] = {
0 };
int k1 = 0, k2 = 0;
int exgcd(int a, int b, int &x, int &y){
if(!b) {
x = 1, y = 0; return a; }
int d = exgcd(b, a % b, x, y);
int z = x; x = y, y = z - y * (a / b);
return d;
}
signed main(){
n = in; int ans = 0, lcm = 0;
for(int i = 1; i <= n; i++) m[i] = in, a[i] = in;
for(int i = 1; i < n; i++){
k1 = 0, k2 = 0;
int d = exgcd(m[i], m[i + 1], k1, k2);
if((a[i + 1] - a[i]) % d != 0) {
puts("-1"); return 0; }
lcm = m[i] / d * m[i + 1];
a[i + 1] = k1 * (a[i + 1] - a[i]) / d * m[i] + a[i];
a[i + 1] = (a[i + 1] % lcm + lcm) % lcm; m[i + 1] = lcm;
}
int y = 0;
exgcd(1, m[n], ans, y);
write((ans * a[n] + m[n]) % m[n]);
return 0;
}
边栏推荐
- Detailed explanation of the use of Oracle's windowing function (2)
- DDL:CREATE 创建数据库——《mysql 从入门到内卷再到入土》
- Kubernetes Notes / Getting Started / Production Environment / Installing Kubernetes with Deployment Tools / Starting a Cluster with kubeadm / Creating a Cluster with kubeadm
- 大小端的理解以及宏定义实现的理解
- 2021年中国工业互联网安全大赛(福建省选拔赛) 暨首届福建省工业互联网创新大赛
- 深度学习实战教程(一):感知器
- 化学制品制造业数智化供应链管理系统:建立端到端供应链采购一体化平台
- npm WARN config global `--global`, `--local` are deprecated. Use `--location=global` instead.
- [SWPUCTF 2021 新生赛] web
- DELETE:删除操作语法&使用例——《mysql 从入门到内卷再到入土》
猜你喜欢
设备管理中数据聚类处理
C语言详解系列——关于调试那些事
Future与CompletableFuture
npm warn config global `--global`, `--local` are deprecated. use `--location=global` instead.
Single-click to cancel the function
详叙c中的分支与循环
数据标注太昂贵?这个方法可以用有限的数据训练模型实现基于文本的ReID!
知识图谱Knowledge Graph
PROCEDURE :存储过程结构——《mysql 从入门到内卷再到入土》
JS中的filter、map、reduce
随机推荐
Before implementing MES management system, these three questions to consider
【nvm】【node多版本管理工具】使用说明和踩坑(exit status 1)
Are you hungry - Institution tree radio
爬虫基本原理介绍、实现以及问题解决
优雅退出在Golang中的实现
[mysql] 深入分析MySQL版本控制MVCC规则
TCL:事务的特点,语法,测试例——《mysql 从入门到内卷再到入土》
LeetCode 1-10题
2021DozerCTF
C语言系列——猜名次、猜凶手、打印杨辉三角
Date picker component (restrict year to set only displayed months)
第四届红帽杯网络安全大赛
Kyligence 通过 SOC 2 Type II 审计,以可信赖的企业级产品服务全球客户
Rider调试ASP.NET Core时报thread not gc-safe的解决方法
npm‘ 不是内部或外部命令,也不是可运行的程序 或批处理文件
详叙c中的分支与循环
The evolution history of Go programmers
PostgreSQL 介绍
MySQL查询数据库中的表和字段
单选点击可取消功能