由韩信点兵到中国剩余定理再到逆元

韩信点兵的小故事

3人报数五人报数七人报数

各余a b c，求军队可能最少人数

物不知其数问题出自一千六百年前我国古代数学名著《孙子算经》.原题为：”今有物不知其数,三三数之二,五五数之三,七七数之二,问物几何?”

例如我国明朝数学家程大位在他著的《算法统宗》（1593年）中就用四句很通俗的口诀暗示了此题的解法：
三人同行七十稀,
五树梅花甘一枝,
七子团圆正半月,
除百零五便得知.

（d=70×a+21×b+15×c >105）mod105;

最后的 d 为所求值。

70 21 15 怎么来的呢》？如下中国剩余定理

是整数m1,m2, ... ,mn的乘积，并设

是除了mi以外的n- 1个整数的乘积。

设

为

模

的数论倒数(

为

模

意义下的逆元)

方程组

的通解形式为

在模

的意义下，方程组

只有一个解：

x= a*2*35+b*1*21+c*1*15

例如：试求一数,使之用4除余m,用5除余n,用7除余k ，

由以上方法可得（105m+56n+120k ）mod 140

（一组值m，n，k 3 2 5 ，该数为（（105*3+ 56*2+120*5）mod 140 = 47 .）

剩余定理给出的通解形式关键是求出 ti 即（Mi 模 mi 意义下的逆元）

so？问题又转到了求逆元

欧几里得求逆元 https://www.cnblogs.com/cenariusxz/p/4323872.html

#include<stdio.h>
#define ll long long

void gcd(ll a,ll b,ll& d,ll& x,ll& y){
    if(!b){d=a;x=1;y=0;}
    else {gcd(b,a%b,d,y,x);y-=x*(a/b);}
}

int main(){
    ll a,b,d,x,y;
    while(scanf("%lld%lld",&a,&b)!=EOF){
        gcd(a,b,d,x,y);
        printf("%lld*%lld+%lld*%lld=%lld
",a,x,b,y,d);
    }
    return 0;
}

View Code

欧几里得快速幂费马小定理求逆元

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long ll;

ll extendGcd(ll a,ll b,ll &x,ll &y){
    ll ans,t;
    if(b==0){
        x=1;y=0;
        return a;
    }
    ans=extendGcd(b,a%b,x,y);
    t=x;x=y;y=t-(a/b)*y;
    return ans;
}
//返回x，a*x=1(mod m)
ll getInv(ll a,ll m){
    ll x,y,d;
    d=extendGcd(a,m,x,y);
    if(d==1)
        return (x%m+m)%m;
    else
        return -1;
}
long long euler(long long x)
{
    long long res=x;
    for(long long i=2;i<(int)sqrt(x*1.0)+1;i++)
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0)
                x/=i;
        }
    if(x>1)
        res=res/x*(x-1);
    return res;
}
//如果m是1000000007这样的素数用费小求逆元
long long quickpowmod(long long x, long long y, long long mod)
{
      long long ret = 1;
      while(y){
         if(y&1)
             ret = ret*x%mod;
         x = x*x%mod;
         y >>= 1;
     }
     return ret;
 }


int main()
{
    ll a,m;
    while(cin>>a>>m){
        cout<<getInv(a,m)<<endl;  //m不是素数
        cout<<quickpowmod(a,m-2,m)<<endl; //m是素数
    }

    return 0;
}

---------------------

本文来自 奶瓶他哥 的CSDN 博客 ，全文地址请点击：https://blog.csdn.net/naipp/article/details/51880008?utm_source=copy

由韩信点兵 到中国剩余定理 再到逆元

由韩信点兵到中国剩余定理再到逆元