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

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

点击量:55

 

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

 

题目描述

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

 

题解:

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

 

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

 

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

 

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

 

2
说点什么

avatar
2 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

… [Trackback]

[…] Here you will find 28476 more Info on that Topic: wjyyy.top/1255.html […]

trackback

… [Trackback]

[…] Info to that Topic: wjyyy.top/1255.html […]

/* */