洛谷 P3868 [TJOI2009]猜数字 题解【同余】【逆元】【中国剩余定理】【快速乘】

点击量：1126

    假装中国剩余定理入了门。。。

目录

题目描述

现有两组数字，每组k个，第一组中的数字分别为：a1，a2，…，ak表示，第二组中的数字分别用b1，b2，…，bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n，满足对于任意的i，n – ai能被bi整除。

 

输入输出格式

输入格式：
输入数据的第一行是一个整数k，（1 ≤ k ≤ 10）。接下来有两行，第一行是：a1，a2，…，ak，第二行是b1，b2，…，bk

 

输出格式：
输出所求的整数n。

 

输入输出样例

输入样例#1：

3
1 2 3
2 3 5

输出样例#1：

23

说明

所有数据中，第一组数字的绝对值不超过10⁹（可能为负数），第二组数字均为不超过6000的正整数，且第二组里所有数的乘积不超过10¹⁸

每个测试点时限1秒

注意：对于C/C++语言，对64位整型数应声明为long long，如使用scanf, printf函数（以及fscanf, fprintf等），应采用%lld标识符。

题解：

    题目要求找出$ n$使得对所有$ i,n\equiv a_i(\mod b_i)$，就是在解线性同余方程组。除了用扩展欧几里得，还可以用中国剩余定理。

    中国剩余定理的解总是构造的。设$ M=\prod\limits_{i=1}^nb_i$，则$ M_i=M/b_i$。这样一来，$ M_i$对除了$ a_i$以外的所有数取模都是0，对其他方程没有影响。我们为了让$ n\equiv a_i(\mod b_i)$，就要构造出$ n$的一个部分来，因为这个部分对其他方程没有影响，因此可以叠加。设$ n$的这一部分为$ p$，则$ p\equiv a_i(\mod b_i)$而因为$ pp^{-1}\equiv 1(\mod b_i)$，因此这个$ p$就被构造为$ p=a_ia_i^{-1}M_i(\mod b_i)$。显然对于所有的$ j\in [1,i)\bigcup(i,n] ,b_j|M_i$。因此我们只要把所有的$ p$算出来相加，就是一个解。而因为所有$ b_i|M$，所以$ n$的解是$ \sum\limits_{i=1}^n p_i+kM,k\in \mathbb{Z}$。

    详细证明可以看其他的课件或论文，这里只是简单提一下思路。

    同时我们看到这个题中有两个特殊条件，一是$ a_i$有可能为负，二是在$ b_i\times a_ia_i^{-1}(\mod b_i)$后可能会爆long long。第一个解决方案就是让$ a_i=a_i+kx,k\in \mathbb{Z}$，找到最小的正整数$ a_i$。第二个就要用到快速乘了。我们在上面的过程中提到了最小正整数解是要$ \mod M$的，题目告诉我们$ M\le 10^{18}$，因此我们在快速乘的过程中，每次$ \mod M$就可以了。

Code：

#include<cstdio>
#include<cstring>
long long a[20],b[20];
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(a==0)
    {
        x=0;
        y=1;
        return b;
    }
    long long d=exgcd(b%a,a,y,x);
    x-=b/a*y;
    return d;
}
long long qmul(long long x,long long y,long long p)
{
    long long ans=0,m=x;
    x%=p;
    while(y)
    {
        if(y&1)
            ans+=m%p;
        ans%=p;
        m*=2;
        m%=p;
        y>>=1;
    }
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);

    for(int i=1;i<=n;i++)
        scanf("%lld",&b[i]);
    long long pi=1;
    for(int i=1;i<=n;i++)
    {
        pi*=b[i];
        a[i]=(a[i]+b[i])%b[i];//处理负数
    }

    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        long long x,y;
        long long d=exgcd(pi/b[i],b[i],x,y);
        x*=d,y*=d;
        //x就是m[i]modb[i]的乘法逆元
        x=(x%b[i]+b[i])%b[i];
        sum+=qmul(qmul(x,a[i],pi),pi/b[i],pi)%pi;
    }
    printf("%lld\n",sum%pi);
    return 0;
}