数论基础——中国剩余定理

朴灿烈づ我的快乐病毒、 2024-04-18 21:14 76阅读 0赞

题目衔接:[https://hihocoder.com/problemset/problem/1303][https_hihocoder.com_problemset_problem_1303]

> 题目描述：
> 
> 时间限制:10000ms
> 
> 单点时限:1000ms
> 
> 内存限制:256MB
> 
> 描述
> 
> 小Ho：今天我听到一个挺有意思的故事！
> 
> 小Hi：什么故事啊？
> 
> 小Ho：说秦末，刘邦的将军韩信带领1500名士兵经历了一场战斗，战死四百余人。韩信为了清点人数让士兵站成三人一排，多出来两人；站成五人一排，多出来四人；站成七人一排，多出来六人。韩信立刻就知道了剩余人数为1049人。
> 
> 小Hi：韩信点兵嘛，这个故事很有名的。
> 
> 小Ho：我觉得这里面一定有什么巧妙的计算方法！不然韩信不可能这么快计算出来。
> 
> 小Hi：那我们不妨将这个故事的数学模型提取出来看看？
> 
> 小Ho：好！
> 
> <小Ho稍微思考了一下>
> 
> 小Ho：韩信是为了计算的是士兵的人数，那么我们设这个人数为x。三人成排，五人成排，七人成排，即x mod 3, x mod 5, x mod 7。也就是说我们可以列出一组方程：
> 
>     x mod 3 = 2
>     x mod 5 = 4
>     x mod 7 = 6
> 
> 韩信就是根据这个方程组，解出了x的值。
> 
> 小Hi：嗯，就是这样！我们将这个方程组推广到一般形式：**给定了n组除数m\[i\]和余数r\[i\]，通过这n组(m\[i\],r\[i\])求解一个x，使得x mod m\[i\] = r\[i\]。**
> 
> 小Ho：我怎么感觉这个方程组有固定的解法？
> 
> 小Hi：这个方程组被称为**模线性方程组**。它确实有固定的解决方法。不过在我告诉你解法之前，你不如先自己想想怎么求解如何？
> 
> 小Ho：好啊，让我先试试啊！
> 
> [提示：模线性方程组][Link 1]

> 输入
> 
> 第1行：1个正整数, N，2≤N≤1,000。
> 
> 第2..N+1行：2个正整数, 第i+1行表示第i组m,r，2≤m≤20,000,000，0≤r<m。
> 
> 计算过程中尽量使用64位整型。
> 
> 输出
> 
> 第1行：1个整数，表示满足要求的最小X，若无解输出-1。答案范围在64位整型内。
> 
> 样例输入
> 
>     3
>     3 2
>     5 3
>     7 2
> 
> 样例输出
> 
>     23

> 题目大意：中文题意，没啥好说的
> 
> 思路：由题意可得这是一道中国剩余定理，而且题目已经将伪代码给出，所以只需要按照伪代码实现即可，扩展欧几里得和欧几里得算法一敲出来，这题就基本ok了。
> 
> PS：不知道为啥，用其它方法就是wa好像只有用题目所给伪代码实现才可

/*
    解题思路：
    */
    #include<set>
    #include<map>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define inf 0x3f3f3f
    #define bug  printf("bug\n")
    const int maxn=1e6+10;
    const double pi=acos(-1.0);
    const double esp=1e-6;
    const int N=2e2+10;
    ll m[maxn],r[maxn];
    int n;
    ll gcd(ll a,ll b)
    {
        while(b)
        {
            ll c=a%b;
            a=b;
            b=c;
        }
        return a;
    }
    void exgcd(ll a,ll b,ll &x,ll &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return ;
        }
        ll x1,y1;
        exgcd(b,a%b,x1,y1);
        x=y1;
        y=x1-(a/b)*y1;
    }
    ll exract()
    {
        ll M=m[1],R=r[1],d,k1,k2,c;
        for(int i=2; i<=n; i++)
        {
            d=gcd(M,m[i]);
            c=r[i]-R;
            if(c%d)
                return -1;
            exgcd(M/d,m[i]/d,k1,k2);
            k1=(c/d*k1)%(m[i]/d);
            R=R+k1*M;
            M=M/d*m[i];
            R%=M;
        }
        if(R<0)
            R=R+M;
        return R;
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%lld %lld",&m[i],&r[i]);
        ll ans=exract();
        printf("%lld\n",ans);
        return 0;
    }

[https_hihocoder.com_problemset_problem_1303]: https://hihocoder.com/problemset/problem/1303
[Link 1]: https://hihocoder.com/problemset/problem/1303#