中国剩余定理

标签：剩余 定理 除以 a1 k1 m1 中国 ll

一、概念

   孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

   有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

   译文：现在有一个数不知道是多少，只知道这个数除以3余2，除以5余3，除以7余2， 问这个数是多少？

   而那句为大家所熟知的《孙子歌诀》则是由明朝数学程大位根据秦九韶解法编成的：三人同行七十稀，五树梅花廿一支，七子团圆月正半，除百零五使得知。

   歌诀的意思是：将这个数除以3得到的余数乘以70，除以5得到的余数乘以21，除以7得到的余数乘以15，全部加起来后除以105，得到的余数（23）就是答案。

二、定理

  

引入几个定理：

 

 

 

 

 

 

 

 

 

 三、求解方法

1.题目

 

 

 2.思想

 

 

 

 四、实例

1.例题：表达整数的奇怪方式

原题链接

 

 

 2.代码实现

#include <iostream>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll& x, ll& y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= x * a / b;
    return d;
}
ll inline mod(ll a, ll b)
{
    return ((a % b)+ b) % b;//保证模是正数
}
int main()
{
    int n;
    scanf("%d", &n);
    ll a1, m1;//输入第一个方程的参数
    scanf("%lld%lld", &a1, &m1);
    for (int i = 1; i < n; i++)
    {
        ll a2, m2, k1, k2;
        scanf("%lld%lld", &a2, &m2);
        ll d = exgcd(a1, -a2, k1, k2);
        if ((m2 - m1) % d);
        {
            puts("-1");
            return 0;
        }
        k1 = k1 * (m2 - m1) / d;
        k1 = mod(k1, abs(a2 / d));
        m1 = m1 + k1 * a1;
        a1 = abs(a2 * a1 / d);
    }
    printf("%lld", m1);//x = k1 * a1 + m1
    return 0;
}


链接：https://www.acwing.com/solution/content/3539/

           https://blog.csdn.net/m0_53524883/article/details/127315888
参考百度百科：仅限内部使用

 

标签：剩余,定理,除以,a1,k1,m1,中国,ll
From： https://www.cnblogs.com/ddfy198811/p/17028055.html