中国余数定理 2(codevs 3990)

题目描述 Description

Skytree神犇最近在研究中国博大精深的数学。

这时，Sci蒟蒻前来拜访，于是Skytree给Sci蒟蒻出了一道数学题：

给定n个质数，以及k模这些质数的余数。问：在闭区间[a,b]中，有多少个k？最小的k是多少？

Sci蒟蒻数学能力差了Skytree三条街，所以他只好寻求计算机的帮助。他发邮件给同为oier的你，你能帮他解决这个问题吗？

输入描述 Input Description

输入第一行为三个正整数n、a、b。

第2到n+1行，每行有两个整数，分别代表第n个质数和k模第n个质数的余数。

输出描述 Output Description

输出为两个整数，代表闭区间[a,b]中k的个数和闭区间[a,b]中最小的k。如果k不存在，则输出两个0。

样例输入 Sample Input

样例1：

3 2 28

3 2

5 3

7 2

样例2：

3 24 31

3 2

5 3

7 2

样例输出 Sample Output

样例1：

样例2：

数据范围及提示 Data Size & Hint

1<=a<=b<=10^14

n<=10

输入保证所有n个质数的乘积<=10^14

每个质数<=1.5*10^9

请无视通过率（被人黑了。。。）

数据保证不会溢出64bit整数

/*

   中国剩余定理

   第一次求的ans是最小正整数解

*/

#include<cstdio>

#include<iostream>

#define N 15

#define LL long long

using namespace std;

LL M[N],m[N],t[N],a[N],sum=,x,y,la,lb,ans;

int n;

void e_gcd(LL a,LL b,LL &x,LL &y)

{

    if(b==)

    {

        x=;y=;

        return;

    }

    e_gcd(b,a%b,x,y);

    LL t=x;x=y;y=t-a/b*y;

}

int main()

{

    cin>>n>>la>>lb;

    for(int i=;i<=n;i++)

    {

        cin>>m[i]>>a[i];

        sum*=m[i];

    }

    for(int i=;i<=n;i++)

    {

        M[i]=sum/m[i];

        e_gcd(M[i],m[i],x,y);

        t[i]=(x+m[i])%m[i];

        ans=((ans+(a[i]%sum)*(t[i]%sum)*(M[i]%sum))%sum);

    }

    LL tot=;

    while(ans<la)ans+=sum;

    LL temp=ans;

    while(ans<=lb)

    {

        ans+=sum;

        tot++;

    }

    if(!tot)temp=;

    cout<<tot<<endl<<temp;

    return ;

}

巴特西

中国余数定理 2(codevs 3990)

最新文章

热门文章