中國剩余定理
中國剩余定理又稱中國余數定理，是數論中一個關于一元線性同余方程組的定理，說明了一元線性同余方程組有解的準則以及求解方法，
求解方法
中國剩余定理原理
主要用到兩個定理：
a mod b = c 等價于 (a + nb) mod b = c;
a mod b = c 等價于 2a mod 2b = 2c;
中國剩余定理代碼表示
void Gcd(int a, int b, int &x, int &y){
//根據歐幾里德定理
if(b == 0){//任意數與0的最大公約數為其本身，
x = 1;
y = 0;
}else{
int x1, y1;
Gcd(b, a % b, x1, y1);
if(a*b < 0){//異號取反
x = - y1;
y = a/b*y1 - x1;
}else{//同號
x = y1;
y = x1 - a/b* y1;
}
}
}
// a為被除陣列，m為余數，k為被除陣列個數1
int China_res_con(int a[],int m[],int k)
{
int N[k];
int min_com_mult = 1; //最小公倍數
int result = 0;
for(int i = 0;i < k;i++)
{
min_com_mult *= m[i];
}
for(int j = 0;j < k; j++)
{
int L, J;
Gcd(min_com_mult/m[j],-m[j],L,J);
N[j] = m[j] * J + 1;//1
N[j] = mm/m[j] * L;//2 【注】1和2這兩個值應該是相等的，
result += N[j]*a[j];
}
return result % min_com_mult;
}
參考文獻
[1] 演算法導論（第三版）
[2] hard_man.中國剩余定理(孫子定理)的證明和c++求解.2012.07.10
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/22015.html
標籤：java
上一篇：c語言學習之可變陣列