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

作者: wjyyy 分类: 中国剩余定理,二进制,同余,快速乘,解题报告,逆元 发布时间: 2018-08-09 20:05

点击量:19

 

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

 

题目描述

现有两组数字,每组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

说明

所有数据中,第一组数字的绝对值不超过109(可能为负数),第二组数字均为不超过6000的正整数,且第二组里所有数的乘积不超过1018

每个测试点时限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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */