当前位置:网站首页>Chinese Remainder Theorem (Sun Tzu theorem) principle and template code
Chinese Remainder Theorem (Sun Tzu theorem) principle and template code
2022-07-06 07:59:00 【Alkali!】
Background
Sun Tzu theorem is ancient China Solve the group of primary congruences Methods . Is an important theorem in number theory . Also known as Chinese Remainder Theorem . The system of Linear Congruence Equations with one variable can be seen in the northern and Southern Dynasties of China ( A.D. 5 century ) Mathematical works of 《 Sun Tzu's Sutra 》 Volume II question 26 , be called “ I don't know the number of things ” problem , The text is as follows :
I don't know the number of things , Two out of three , Three out of five , Two of the seven . Query geometry ? namely , An integer divided by three and two , Divide by five and three , Divide by seven and two , Find this integer .《 Sun Tzu's Sutra 》 The problem of Congruence Equations is mentioned for the first time , And the solution of the above specific problems , Therefore, the Chinese remainder theorem will also be called the Sun Tzu theorem in the Chinese mathematical literature .
principle
Template code
#include<iostream>
using namespace std;
typedef long long LL; // The data range is quite large , Here we use long long
LL exgcd(LL a,LL b,LL &x,LL &y) // extended euclidean algorithm
{
if(!b)
{
x=1,y=0;
return a;
}
LL ans=exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-a/b*y;
return ans;
}
LL mod(LL a,LL b) // Guarantee a%b The value after taking the module must be non negative
{
return (a%b+b)%b;
}
int n;
int main()
{
scanf("%d",&n);
LL m1,a1,m2,a2,k1,k2;
scanf("%lld%lld",&a1,&m1);
for(int i=1;i<n;i++)
{
scanf("%lld%lld",&a2,&m2);
LL d=exgcd(a1,-a2,k1,k2);
if((m2-m1)%d) // If it's not divisible , Explain that there is no solution
{
printf("%d",-1);
return 0;
}
k1=mod(k1*(m2-m1)/d,abs(a2/d)); // Take mold at any time , Ensure the minimum number in the calculation process , Give Way k The value of is always optimal
m1=k1*a1+m1; // At this time m and a After the merger x In the expression m and a
a1=abs(a1/d*a2); //
}
printf("%lld",mod(m1,a1)); // The answer is this
return 0;
}
边栏推荐
- Easy to use tcp-udp_ Debug tool download and use
- NFT smart contract release, blind box, public offering technology practice -- jigsaw puzzle
- Launch APS system to break the problem of decoupling material procurement plan from production practice
- 链表面试题(图文详解)
- MySQL view tablespace and create table statements
- Cf1036c class numbers solution
- Redis list detailed explanation of character types yyds dry goods inventory
- It's hard to find a job when the industry is in recession
- File upload of DVWA range
- Database addition, deletion, modification and query
猜你喜欢
Learn Arduino with examples
NFT smart contract release, blind box, public offering technology practice -- jigsaw puzzle
861. Score after flipping the matrix
Generator Foundation
23. Update data
Comparison of usage scenarios and implementations of extensions, equal, and like in TS type Gymnastics
[redis] Introduction to NoSQL database and redis
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Golang DNS 随便写写
Opencv learning notes 9 -- background modeling + optical flow estimation
随机推荐
华为云OBS文件上传下载工具类
21. Delete data
Wonderful use of TS type gymnastics string
Compliance and efficiency, accelerate the digital transformation of pharmaceutical enterprises, and create a new document resource center for pharmaceutical enterprises
CAD ARX gets the current viewport settings
What are the ways to download network pictures with PHP
Codeforces Global Round 19(A~D)
Common functions for PHP to process strings
How to prevent Association in cross-border e-commerce multi account operations?
Webrtc series-h.264 estimated bit rate calculation
Database basic commands
Yu Xia looks at win system kernel -- message mechanism
(lightoj - 1410) consistent verbs (thinking)
Nft智能合约发行,盲盒,公开发售技术实战--拼图篇
Luogu p4127 [ahoi2009] similar distribution problem solution
二叉树创建 & 遍历
软件开发的一点随记
MES, APS and ERP are essential to realize fine production
http缓存,强制缓存,协商缓存
Nft智能合约发行,盲盒,公开发售技术实战--合约篇