【codevs3990】中国余数定理2

http://prayer.hustoj.com/problem.php?cid=1107&pid=31 本来要颓csgo，然后逛了一下prayeroj，发现小学生连中国剩余定理都会了，吓了一跳，让后学习的动力就来了； 我可不想在以后高一的时候给初三爷端茶；

---

中国剩余定理

可以证明这一个x%M在模M域下是唯一解（因为相邻解相差M） 所以可以发现不在模域下时，x%M是最小解（不成你来负数？）

---

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<cstring> #include<map> #define Ll long long using namespace std; Ll a[11],m[11]; Ll n,x,y,mi,l,r,ans,M; Ll read() { Ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void exgcd(Ll a,Ll b,Ll &x,Ll &y){ if(!b){x=1;y=0;return;} exgcd(b,a%b,x,y); Ll X=x; x=y; y=X-a/b*y; } int main() { n=read();l=read();r=read(); M=1; for(int i=1;i<=n;i++)m[i]=read(),a[i]=read(),M*=m[i]; for(int i=1;i<=n;i++){ mi=M/m[i]; exgcd(mi,m[i],x,y); x=(x%m[i]+m[i])%m[i]; ans+=(a[i]%M*x%M)%M*mi; ans%=M; } if(ans<l||ans>r)printf("0\n0");else printf("%lld\n%lld",(r-ans)/M+1,ans); }