对于一个数x，知道：
x%m1=a1,x%m2=a2,x%m3=a3.(m1,m2,m3)互质。
求x。
我们来形象化一下：
一个数，%3=1，%5=1，%7=2，这个数是什么？
稍微试一试发现是16，那么怎么正常地算出来呢？
我们首先要弄明白一件事：
如果a%b==c，那么a加上一个b的倍数，%b还是余c。这个还是很显而易见的吧。
那我我们想要求出的x，可以分为三个数相加
x=A1+A2+A3.其中A1%3=1，A2%5=1，A3%7=2.A2、3是3的倍数，A1、3是5的倍数，A1、2是7的倍数。
我们先求A3，A3要满足是5、3的倍数，也要满足%7=2,。
首先，我们知道它一定是15的倍数，那么我们要知道怎样才能满足%7=2
如果要求%7=2，只用求出来%7=1，然后再乘2就可以了。
于是得到了如下方程
15*t≡1(mod 7)
似曾相识，这个方程相当于15*t+7*y=1可以用拓展欧几里得求解。
然后，我们知道t=1,也就是15*1%7=1,所以15*1*2%7就等于2.
于是A3就等于15*1*2=30，
以此类推，求出来A1、A2，最后加起来就是答案。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> #define REP(i,k,n) for(LL i=k;i<=n;i++) #define in(a) a=read() using namespace std; typedef long long LL; inline LL read(){ LL x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } LL T; inline void exgcd(LL A,LL B,LL &x,LL &y){ if(B==0) x=1,y=0; else exgcd(B,A%B,x,y),T=x,x=y,y=T-A/B*y; } LL n,a[50],b[50],m[50],t[50]; LL M=1,ans; int main(){ in(n); REP(i,1,n) in(a[i]),in(b[i]),M=M*a[i]; REP(i,1,n){ m[i]=M/a[i]; LL x,y; exgcd(m[i],a[i],x,y); t[i]=x; ans=((ans+(b[i]*t[i]*m[i])%M+M)%M)%M; } cout<<ans; return 0; } /*3 3 1 5 1 7 2*/
转载于:https://www.cnblogs.com/jason2003/p/10552476.html
相关资源：JAVA上百实例源码以及开源项目