【codevs3990】中国余数定理2

【题目描述】
Skytree神犇最近在研究中国博大精深的数学。
这时，Sci蒟蒻前来拜访，于是Skytree给Sci蒟蒻出了一道数学题：
给定n个质数，以及k模这些质数的余数。问：在闭区间[a,b]中，有多少个k？最小的k是多少？
Sci蒟蒻数学能力差了Skytree三条街，所以他只好寻求计算机的帮助。他发邮件给同为oier的你，你能帮他解决这个问题吗？

【题解】

用中国剩余定理求出最小的k，然后k+M*y都是可能的值，所以个数就是（b-k）/M+1

注意在统计答案时，由于模数M可能过大，要使用快速乘。

 /*************

   CODEVS 3990

   by chty

   2016.11.1

 *************/

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<ctime>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 ll n,l,r,ans,M(),a[],m[];

 inline ll read()

 {

     ll x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

 void exgcd(ll a,ll b,ll &x,ll &y)

 {

     if(b==)  {x=; y=; return;}

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

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

 }

 ll mul(ll x,ll y){return ((x*y-(ll)(((long double)x*y+0.5)/M)*M)%M+M)%M;}//一行快速乘

 int main()

 {

     freopen("cin.in","r",stdin);

     freopen("cout.out","w",stdout);

     n=read();  l=read();  r=read();

     for(ll i=;i<=n;i++)  m[i]=read(),a[i]=read(),M*=m[i];

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

     {

         ll x,y,Mi=M/m[i];

         exgcd(Mi,m[i],x,y);

         ans=(ans+mul(mul(x,Mi),a[i]))%M;

     }

     if(ans<l||ans>r)  printf("0\n0\n");

     else printf("%lld\n%lld\n",(r-ans)/M+,ans);

 }