扩展中国剩余定理（EXCRT）

基本信息

源码名称：扩展中国剩余定理（EXCRT）

源码大小：0.66KB

文件格式：.cpp

开发语言：C/C++

更新时间：2021-07-21

友情提示：（无需注册或充值，赞助后即可获取资源下载链接）

嘿，亲！知识可是无价之宝呢，但咱这精心整理的资料也耗费了不少心血呀。小小地破费一下，绝对物超所值哦！如有下载和支付问题，请联系我们QQ(微信同号)：813200300

本次赞助数额为： 2 元　

源码介绍

拓展中国剩余定理模板

给定 n 组非负整数 $a_{i} b_{i}$ 求解关于x的方程组的最小非负整数解。

$x \equiv b_{1} (m o d a_{1})$

$x \equiv b_{2} (m o d a_{2})$

$. . .$

$x \equiv b_{n} (m o d a_{n})$

void doit(){

exgcd(x,y,a,A);

ll tmp=A/d;

x=x*(B-b)/d%tmp;

x=(x%tmp tmp)%tmp;

tmp=lcm(a,A);

b=(a*x b)%tmp;

b=(b%tmp tmp)%tmp;

a=tmp;

}