非启发式算法——中国剩余定理

简介: 非启发式算法——中国剩余定理

探秘中国剩余定理

中国剩余定理(Chinese Remainder Theorem,CRT)是一种用于求解一组同余方程组的数学工具。它在密码学、编码理论、计算机科学等领域有着广泛的应用。在本篇博客中,我们将深入了解中国剩余定理的原理、应用场景,并提供使用C、Java、Python和Go语言的模板。

1. 中国剩余定理的原理

1.1 同余方程组

同余方程组是指一组形如:

1.2 中国剩余定理的表述

1.3 原理解释

中国剩余定理的核心思想是通过处理两两互质的模数,将问题转化为多个简单同余方程的组合,从而降低了计算的复杂度。

2. 应用场景

中国剩余定理广泛应用于密码学、信息安全、计算机图形学等领域。其高效的特性使其成为一种常用的数学工具。

3. 模板代码

接下来,我们提供使用C、Java、Python和Go语言的中国剩余定理模板代码。

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启发式算法中爬山法的讲解及解方程问题实战(超详细 附源码)
Python启发式算法中爬山法的讲解及解方程问题实战(超详细 附源码)
67 0
|
3月前
|
算法 NoSQL 容器
启发式搜索: A*算法
启发式搜索: A*算法
|
6月前
|
算法 数据可视化 Java
数学建模常用算法:启发式优化算法合辑(内含多种智能优化算法,使用java实现算法、详细注释、并进行结果可视化)
数学建模常用算法:启发式优化算法合辑(内含多种智能优化算法,使用java实现算法、详细注释、并进行结果可视化)
143 2
|
2月前
|
算法 Java Go
非启发式算法——旅行商问题(TSP)及其解决算法
非启发式算法——旅行商问题(TSP)及其解决算法
56 0
|
2月前
|
存储 算法 决策智能
非启发式算法学习知识目录
非启发式算法学习知识目录
36 0
|
9月前
|
算法
使用HGS算法调整PD控制器增益的无人机动态性能数据——基于启发式的无人机路径跟踪优化(Matlab代码实现)
使用HGS算法调整PD控制器增益的无人机动态性能数据——基于启发式的无人机路径跟踪优化(Matlab代码实现)
使用HGS算法调整PD控制器增益的无人机动态性能数据——基于启发式的无人机路径跟踪优化(Matlab代码实现)
|
9月前
|
算法
配电网重构|基于新颖的启发式算法SOE的随机(SDNR)配电网重构(Matlab代码实现)【算例33节点、84节点、119节点、136节点、417节点】
配电网重构|基于新颖的启发式算法SOE的随机(SDNR)配电网重构(Matlab代码实现)【算例33节点、84节点、119节点、136节点、417节点】
|
9月前
|
算法
非洲秃鹫优化算法:求解全局优化问题的一种新的自然启发元启发式算法(Matlab代码实现)
非洲秃鹫优化算法:求解全局优化问题的一种新的自然启发元启发式算法(Matlab代码实现)
198 0
|
9月前
|
算法
开源代码分享(5)—配电网重构的启发式算法(附matlab代码)
本文提出了一种两阶段的启发式计算方法,可以在最小的计算时间内重新配置一个径向分布网络。所有的网络交换机在操作的初始阶段都是关闭的,并提出了一个顺序的开关开闸策略,以获得一个接近最优的径向配置。在随后的阶段中,从径向网络中选择一对开关来交换其开/关状态。提出了一种利用总线注入分支电流矩阵的数学模型,选择一对交换机,目的是减少每次交换操作后网络的功率损耗。该方法在33总线、69总线、84总线、136总线和417总线的配电网上进行了测试,结果表明,所提的方法有助于在明显较低的运行时间下实现径向配电网的最佳配置。
|
9月前
|
负载均衡 监控 算法
转:启发式算法对网络行为管理系统的应用研究、实用性分析及实现难度
启发式算法在网络行为管理系统中的应用研究是一个重要的领域,它可以帮助改善系统的性能和效率。启发式算法是一种通过模拟自然界的演化过程或启发式规则来解决复杂问题的方法。
56 2