3990 中国余数定理 2 题目描述 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： 1 23
样例2： 0 0 数据范围及提示 Data Size & Hint 1<=a<=b<=10^14 n<=10 输入保证所有n个质数的乘积<=10^14 每个质数<=1.5*10^9 请无视通过率（被人黑了。。。） 数据保证不会溢出64bit整数

分析

      废话不多说，这是中国剩余定理模板题，直接看过程       模线性方程组解的构造过程如下，       令ji=m1*m2*...*mn，       Mi=ji/mi       ti=Mi在模mi意义下的逆元       方程的最小解如下       ans=ai*ti*Mi%ji       方程的通解为 ai * ti * mi % ji  + k * ji       其中k是非负整数

代码

//CodeVS3990 中国余数定理2 中国剩余定理 #include #define ll long long using namespace std; ll N, A, B, a[15], m[15], cnt, minn, t[15], M[15], ji, ans, tmp; void exgcd(ll a, ll b, ll &x, ll &y) { if(!b){x=1,y=0;return;} exgcd(b,a%b,x,y); ll t=x;x=y;y=t-a/b*y; } int main() { int i; ll x, y; scanf("%lld%lld%lld",&N,&A,&B); ji=1; for(i=1;i<=N;i++) { scanf("%lld%lld",&m[i],&a[i]); ji*=m[i]; } for(i=1;i<=N;i++) { M[i]=ji/m[i]; exgcd(M[i],m[i],x,y); t[i]=(x+m[i])%m[i]; ans=(ans+a[i]*t[i]%ji*M[i]%ji)%ji; } while(ans