Acwing-204-表达整数的奇怪方式(扩展中国剩余定理)

2021-02-02 00:28

阅读：460

标签：c++ i++ 扩展 int std print 中国剩余定理 long 思路

链接:

https://www.acwing.com/problem/content/206/

题意:

给定2n个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数x，满足?i∈[1,n],x≡mi(mod ai)。

思路:

扩展中国剩余定理模板题.

代码:

#include 
using namespace std;
typedef long long LL;

LL R[50], M[50];
int n;

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, x, y);
    LL tmp = y;
    y = x-(a/b)*y;
    x = tmp;
    return d;
}

LL ExCRT()
{
    LL m = M[1], r = R[1], x, y, gcd;
    for (int i = 2;i

Acwing-204-表达整数的奇怪方式(扩展中国剩余定理)

标签：c++ i++ 扩展 int std print 中国剩余定理 long 思路

原文地址：https://www.cnblogs.com/YDDDD/p/11576013.html

上一篇：Windows下常用的命令

下一篇：C#继承overload与override

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Acwing-204-表达整数的奇怪方式(扩展中国剩余定理)
文章链接：http://soscw.com/index.php/essay/49722.html

亲，登录后才可以留言！

Acwing-204-表达整数的奇怪方式(扩展中国剩余定理)

链接:

题意:

思路:

代码:

评论

热门文章

推荐文章

最新文章

置顶文章