「学习笔记」(扩展)中国剩余定理

这篇具有很好参考价值的文章主要介绍了「学习笔记」(扩展)中国剩余定理。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

该问题出自《孙子算经》,具体问题的解答口诀由明朝数学家程大位在《算法统宗》中给出:

三人同行七十希,五树梅花廿一支,七子团圆正半月,除百零五便得知。

\(2 \times 70 + 3 \times 21 + 2 \times 15 = 233 = 2 \times 105 + 23\),故答案为 \(23\)

定义

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组(其中 \(n_1, n_2, \cdots, n_k\) 两两互质):

\[\begin{cases} x \bmod p_1 = a_1\\ x \bmod p_2 = a_2\\ \cdots\\ x \bmod p_n = a_n\\ \end{cases} \]

过程

对于方程

\[\begin{cases} x \bmod p_1 = a_1\\ x \bmod p_2 = a_2\\ \end{cases} \]

我们可以得知 \(x = k_1 p_1 + a_1 = k_2 p_2 + a_2\),进而推出 \(k_1 p_1 - k_2 p_2 = a_2 - a_1\)
我们观察这个式子,是不是跟 \(xa + yg = g\) 很像?
我们可以用扩展欧几里得算法来做。
扩展欧几里得算法代码

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int xp, yp;
    int g = exgcd(b, a % b, xp, yp);
    x = yp, y = xp - yp * (a / b);
    return g;
}

中国剩余定理代码

void calc(ll a1, ll b1, ll a2, ll b2, ll& tmpa, ll& tmpb) {
    ll ansx, ansy, g;
    g = exgcd(a1, a2, ansx, ansy);
    ansy = -ansy;
    if ((b2 - b1) % g) {
        tmpa = tmpb = -1;
        return ;
    }
    tmpa = a1 / g * a2;
    ll k = (b2 - b1) / g;
    ansx = qtimes(ansx, k, tmpa);
    ansy = qtimes(ansy, k, tmpa);
    ll ans = (qtimes(a1, ansx, tmpa) + b1) % tmpa;
    tmpb = (ans % tmpa + tmpa) % tmpa;
}

通过观察,你会发现,这种解法不需要 \(p_1 \perp p_2\),因此扩展中国剩余定理也是这个解法,这是一种通解。

题目

【模板】扩展中国剩余定理(EXCRT)

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 1e5 + 5;

int n;
ll a[N], b[N];

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

ll qtimes(ll x, ll y, ll mod) {
    ll ans = 0;
    if (y < 0) {
        x = -x;
        y = -y;
    }
    while (y) {
        if (y & 1) {
            ans = (ans + x) % mod;
        }
        y >>= 1;
        x = (x + x) % mod;
    }
    return ans;
}

void calc(ll a1, ll b1, ll a2, ll b2, ll& tmpa, ll& tmpb) {
    ll ansx, ansy, g;
    g = exgcd(a1, a2, ansx, ansy);
    ansy = -ansy;
    if ((b2 - b1) % g) {
        tmpa = tmpb = -1;
        return ;
    }
    tmpa = a1 / g * a2;
    ll k = (b2 - b1) / g;
    ansx = qtimes(ansx, k, tmpa);
    ansy = qtimes(ansy, k, tmpa);
    ll ans = (qtimes(a1, ansx, tmpa) + b1) % tmpa;
    tmpb = (ans % tmpa + tmpa) % tmpa;
}

int main() {
    n = read<int>();
    rep (i, 1, n, 1) {
        a[i] = read<ll>(), b[i] = read<ll>();
    }
    ll lasa = a[1], lasb = b[1];
    rep (i, 2, n, 1) {
        calc(lasa, lasb, a[i], b[i], lasa, lasb);
    }
    cout << lasb << '\n';
    return 0;
}

【模板】中国剩余定理(CRT)/ 曹冲养猪文章来源地址https://www.toymoban.com/news/detail-462515.html

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 1e5 + 5;

int n;
ll a[N], b[N];

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

ll qtimes(ll x, ll y, ll mod) {
    ll ans = 0;
    if (y < 0) {
        x = -x;
        y = -y;
    }
    while (y) {
        if (y & 1) {
            ans = (ans + x) % mod;
        }
        y >>= 1;
        x = (x + x) % mod;
    }
    return ans;
}

void calc(ll a1, ll b1, ll a2, ll b2, ll& tmpa, ll& tmpb) {
    ll ansx, ansy, g;
    g = exgcd(a1, a2, ansx, ansy);
    ansy = -ansy;
    if ((b2 - b1) % g) {
        tmpa = tmpb = -1;
        return ;
    }
    tmpa = a1 / g * a2;
    ll k = (b2 - b1) / g;
    ansx = qtimes(ansx, k, tmpa);
    ansy = qtimes(ansy, k, tmpa);
    ll ans = (qtimes(a1, ansx, tmpa) + b1) % tmpa;
    tmpb = (ans % tmpa + tmpa) % tmpa;
}

int main() {
    n = read<int>();
    rep (i, 1, n, 1) {
        a[i] = read<ll>(), b[i] = read<ll>();
    }
    ll lasa = a[1], lasb = b[1];
    rep (i, 2, n, 1) {
        calc(lasa, lasb, a[i], b[i], lasa, lasb);
    }
    cout << lasb << '\n';
    return 0;
}

到了这里,关于「学习笔记」(扩展)中国剩余定理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • RSA的中国剩余定理(CRT)算法解密

    1.公私钥计算 (1) 计算 n = p x q ; (2) 计算Φ(n)= (p-1) x (q-1); (3) 选择 e ,且e与Φ(n)互素 ; (4) 确定d x e= 1 mod Φ(n); (5) 确定公钥 PU = {n , d}, 私钥 PR = {n,e} 2.加解密 明文M ;加密Y= M^e mod n; 解密 M = Y^d mod n; p和q是互相独立的大素数,n为p*q,对于任意(m1, m2), (0=m1

    2024年02月08日
    浏览(46)
  • RSA-CRT 使用中国剩余定理CRT对RSA算法进行解密

    使用中国剩余定理对RSA进行解密,可以提高RSA算法解密的速度。 有关数论的一些基础知识可以参考以下文章: 密码学基础知识-数论(从入门到放弃) 设p和q是不同的质数,且n = p*q。对于任意(X1, x2),其中 0 ≤ x1 p 和 0 ≤ x2 q,存在数x,其中 0 ≤ x n。 中国剩余定理给出了以下的

    2024年02月04日
    浏览(40)
  • 数论——欧几里得算法、裴蜀定理、扩展欧几里得算法 学习笔记

    最大公约数 最大公约数即为 Greatest Common Divisor,常缩写为 gcd。 一组整数的公约数,是指同时是这组数中每一个数的约数的数。 (pm 1) 是任意一组整数的公约数; 一组整数的最大公约数,是指所有公约数里面最大的一个。 特殊的,我们定义 (gcd(a, 0) = a) 。 最小公倍数 最

    2024年02月08日
    浏览(45)
  • ES9学习 -- 对象的剩余参数与扩展运算符 / 正则扩展 / Promise.finally / 异步迭代

    // kerwin {age:100,location: ‘dalian’} 其中…other 可以拿到对象的剩余参数 // {name: ‘xiaoming’,location: ‘dalian’,age: 18] 在实际开发中,我们会使用ajax() 封装一些默认的属性和属性值,以备用户忘记或未传入某些参数。 // { methods: “get”, async: true, url: “/api”} 正则表达式命名捕获

    2024年04月09日
    浏览(40)
  • 数论——欧拉函数、欧拉定理、费马小定理 学习笔记

    定义 欧拉函数(Euler\\\'s totient function),记为 (varphi(n)) ,表示 (1 sim n) 中与 (n) 互质的数的个数。 也可以表示为: (varphi(n) = sumlimits_{i = 1}^n [gcd(i, n) = 1]) . 例如: (varphi(1) = 1) ,即 (gcd(1, 1) = 1) ; (varphi(2) = 1) ,即 (gcd(1, 2) = 1) ; (varphi(3) = 2) ,即 (gcd(1, 3

    2024年02月08日
    浏览(43)
  • 欧拉定理 & 扩展欧拉定理

    观前提醒 :「文章仅供学习和参考,如有问题请在评论区提出」 目录 前置 剩余类(同余类) 完全剩余系(完系) 简化剩余系(缩系) 欧拉函数 欧拉定理 扩展欧拉定理 参考资料 给定一个正整数 (n) ,把所有的整数根据 模 (n) 的余数 (rin [0, n - 1]) 分为 (n) 类,每一类

    2024年02月13日
    浏览(40)
  • 数论——卢卡斯定理、求组合数 学习笔记

    温馨提示:组合数一般较大,下面的示范代码均无视数据范围,如果爆 int 请自行开 long long 或高精度处理。 从 (n) 个不同元素中,任取 (m) 个元素组成一个集合,叫做从 (n) 个不同元素中取出 (m) 个元素的一个组合;从 (n) 个不同元素中取出 (m leq n) 个元素的所有组合

    2024年02月08日
    浏览(40)
  • 【算法基础 & 数学】快速幂求逆元(逆元、扩展欧几里得定理、小费马定理)

    原文链接 首先,在算法竞赛中,很多情况下会遇到数值很大的数据,这个时候,题目往往会让我们对某个数去摸,来控制数据范围。 在±*运算中,我们可以对每个数单独取模,然后再对运算之后的数取模。 但是除法比较特殊,例如: ( 40 ÷ 5 ) m o d 10 ≠ ( ( 40 m o d 10 ) ÷ ( 5

    2024年01月23日
    浏览(49)
  • ES6 全详解 let 、 const 、解构赋值、剩余运算符、函数默认参数、扩展运算符、箭头函数、新增方法,promise、Set、class等等

    ​ ECMAScript 6.0,简称 ES6,是 JavaScript 语言的下一代标准,已经在 2015 年 6 月正式发布了。它的目标,是使得 JavaScript 语言可以用来编写复杂的大型应用程序,成为企业级开发语言 要讲清楚这个问题,需要回顾历史。1996 年 11 月,JavaScript 的创造者 Netscape 公司,决定将 JavaSc

    2024年04月15日
    浏览(45)
  • MyBatisPlus学习笔记四-扩展功能

       先查询,再分组    

    2024年01月19日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包