# 探秘中国剩余定理

## 3. 模板代码

### 3.1 C语言模板

#include <stdio.h>

// 扩展欧几里得算法，用于计算模逆
long long extended_gcd(long long a, long long b, long long *x, long long *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}

long long x1, y1;
long long gcd = extended_gcd(b, a % b, &x1, &y1);

*x = y1;
*y = x1 - (a / b) * y1;

return gcd;
}

// 计算模逆
long long mod_inverse(long long a, long long m) {
long long x, y;
extended_gcd(a, m, &x, &y);
return (x % m + m) % m;
}

// 中国剩余定理求解
long long chinese_remainder(int num, long long a[], long long m[]) {
long long M = 1;
for (int i = 0; i < num; ++i) {
M *= m[i];
}

long long result = 0;
for (int i = 0; i < num; ++i) {
long long M_i = M / m[i];
long long N_i = mod_inverse(M_i, m[i]);
result = (result + a[i] * M_i * N_i) % M;
}

return (result + M) % M;
}

int main() {
int num = 3;
long long a[] = {2, 3, 2};
long long m[] = {3, 5, 7};

long long result = chinese_remainder(num, a, m);

printf("The solution is: %lld\n", result);

return 0;
}

### 3.2 Java语言模板

public class ChineseRemainderTheorem {

// 扩展欧几里得算法，用于计算模逆
static long extendedGCD(long a, long b,

long[] x, long[] y) {
if (b == 0) {
x[0] = 1;
y[0] = 0;
return a;
}

long[] x1 = new long[1], y1 = new long[1];
long gcd = extendedGCD(b, a % b, x1, y1);

x[0] = y1[0];
y[0] = x1[0] - (a / b) * y1[0];

return gcd;
}

// 计算模逆
static long modInverse(long a, long m) {
long[] x = new long[1], y = new long[1];
extendedGCD(a, m, x, y);
return (x[0] % m + m) % m;
}

// 中国剩余定理求解
static long chineseRemainder(int num, long[] a, long[] m) {
long M = 1;
for (int i = 0; i < num; ++i) {
M *= m[i];
}

long result = 0;
for (int i = 0; i < num; ++i) {
long M_i = M / m[i];
long N_i = modInverse(M_i, m[i]);
result = (result + a[i] * M_i * N_i) % M;
}

return (result + M) % M;
}

public static void main(String[] args) {
int num = 3;
long[] a = {2, 3, 2};
long[] m = {3, 5, 7};

long result = chineseRemainder(num, a, m);

System.out.println("The solution is: " + result);
}
}

### 3.3 Python语言模板

def extended_gcd(a, b):
if b == 0:
return a, 1, 0
else:
gcd, x, y = extended_gcd(b, a % b)
return gcd, y, x - (a // b) * y

def mod_inverse(a, m):
gcd, x, y = extended_gcd(a, m)
return (x % m + m) % m

def chinese_remainder(num, a, m):
M = 1
for i in range(num):
M *= m[i]

result = 0
for i in range(num):
M_i = M // m[i]
N_i = mod_inverse(M_i, m[i])
result = (result + a[i] * M_i * N_i) % M

return (result + M) % M

if __name__ == "__main__":
num = 3
a = [2, 3, 2]
m = [3, 5, 7]

result = chinese_remainder(num, a, m)

print(f"The solution is: {result}")

### 3.4 Go语言模板

package main

import "fmt"

// 扩展欧几里得算法，用于计算模逆
func extendedGCD(a, b int64) (int64, int64, int64) {
if b == 0 {
return a, 1, 0
}

gcd, x, y := extendedGCD(b, a%b)
return gcd, y, x - (a/b)*y
}

// 计算模逆
func modInverse(a, m int64) int64 {
_, x, _ := extendedGCD(a, m)
return (x%m + m) % m
}

// 中国剩余定理求解
func chineseRemainder(num int, a, m []int64) int64 {
M := int64(1)
for i := 0; i < num; i++ {
M *= m[i]
}

result := int64(0)
for i := 0; i < num; i++ {
M_i := M / m[i]
N_i := modInverse(M_i, m[i])
result = (result + a[i]*M_i*N_i) % M
}

return (result + M) % M
}

func main() {
num := 3
a := []int64{2, 3, 2}
m := []int64{3, 5, 7}

result := chineseRemainder(num, a, m)

fmt.Printf("The solution is: %d\n", result)
}

|
4月前
|

Python启发式算法中爬山法的讲解及解方程问题实战（超详细 附源码）
Python启发式算法中爬山法的讲解及解方程问题实战（超详细 附源码）
67 0
|
3月前
|

50 0
|
6月前
|

143 2
|
2月前
|

56 0
|
2月前
|

36 0
|
9月前
|

56 0
|
9月前
|

76 0
|
9月前
|

198 0
|
9月前
|

131 0
|
9月前
|

56 2