题目地址：POJ 2891
题意：给你k组同余关系，每组包含一个ai和ri，让你找出一个最小的数m，满足m%a1=r1，m%a2=r2…….m%ak=rk。
思路：纵观上述公式，很熟悉，其实就是求两两公式之间的最小值，例如K=3，那么先求第一组和第二组的最小，然后合并第一组和第二组，然后用合并之后的再和第三组找最小，最后的结果就是最终的结果。也就是这个题分两部分来完成。
1.找出两组最小。对于m%a1=r1和m%a2=r2可以得出两个公式m=a1*x+r1，m=a2*y+r2(x，y相当于m/ai的次数)，然后联立得到a1*x+a2*y=r2-r1.然后就套用扩展欧几里德得出最小的x。
2.合并。到底如何合并，新式子是这样的：m1mod lcm(a1,a2) ==m，即m1=lcm(a1+a2)*x+m（m1位新要求的值，m为求出来的当前最小的值），然后把x*lcm(a1,a2)赋值给a1，，把m赋值给r1。
#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <sstream>#include <algorithm>#include <set>#include <queue>#include <stack>#include <map>//#pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;LL gcd(LL a,LL b){while(b!=0){LL r=b;b=a%b;a=r;}return a;}LL exgcd(LL a,LL b,LL &x,LL &y){if(b==0){x=1;y=0;return a;}LL r=exgcd(b,a%b,x,y);LL t=x;x=y;y=t-(a/b)*y;return r;}int main(){int n;LL a1,r1,a2,r2;LL a,b,d,r;LL x1,y1,t;while(~scanf("%d",&n)){scanf("%lld %lld",&a1,&r1);if(n==1)printf("%lld\n",a1+r1);else{int flag=0;for(int i=1;i<n;i++){scanf("%lld %lld",&a2,&r2);if(!flag){a=a1;b=a2;d=r2-r1;r=gcd(a,b);if(d%r){flag=1;continue;}a/=r;b/=r;d/=r;exgcd(a,b,x1,y1);x1=x1*d;y1=y1*d;x1=(x1%b+b)%b;//此处用的是b的原因是对于公式a1*x1+a2*y1=m前面的a1*x1可能是负的，所以a1*（x1+a2*n）+a2*（y1-a1*n）=m。r1=a1*x1+r1;a1=a1/r*a2;}}if(flag)puts("-1");elseprintf("%lld\n",r1);}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
你是自由的，不仅是身体上的自由，
