codevs 3990 中国余数定理 2

codevs 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整数 公式： ∑i=1nc[i]×Mm[i]×inv(Mm[i],m[i]) ∑ i = 1 n c [ i ] × M m [ i ] × i n v ( M m [ i ] , m [ i ] ) 最后那个为在%m[i]意义下的逆元 证明就是设n满足%m[i]=1 %Mm[i]=0 M m [ i ] = 0 然后推导通过欧几里得即可得证 ​

#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline ll read(){ ll x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f; }const int N=11;ll M,ans,L,R,c[N];int n,m[N];inline 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;}inline void inc(ll &x,ll v){x=x+v>=M?x+v-M:x+v;}int main(){ freopen("codevs3990.in","r",stdin); n=read();L=read();R=read();M=1; for (int i=1;i<=n;++i) m[i]=read(),M*=m[i],c[i]=read(); for (int i=1;i<=n;++i){ ll x,y,a=M/m[i],b=m[i];exgcd(a,b,x,y); x%=b;(x+=b)%=b;inc(ans,a*x%M*c[i]%M); } if (ansR) {puts("0");puts("0");return 0;} ll nm=(R-ans)/M+1; printf("%lld\n%lld\n",nm,ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。