Hello Kiki（hdu3579+不互质的中国剩余定理）

栏目：php教程时间：2015-05-28 08:38:10

Hello Kiki

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Submit Status Practice HDU 3579

Appoint description:

Description

One day I was shopping in the supermarket. There was a cashier counting coins seriously when a little kid running and singing "门前大桥下游过1群鸭，快来快来数1数，24678". And then the cashier put the counted coins back morosely and count again...
Hello Kiki is such a lovely girl that she loves doing counting in a different way. For example, when she is counting X coins, she count them N times. Each time she divide the coins into several same sized groups and write down the group size Mi and the number of the remaining coins Ai on her note.
One day Kiki's father found her note and he wanted to know how much coins Kiki was counting.

Input

The first line is T indicating the number of test cases.
Each case contains N on the first line, Mi(1 <= i <= N) on the second line, and corresponding Ai(1 <= i <= N) on the third line.
All numbers in the input and output are integers.
1 <= T <= 100, 1 <= N <= 6, 1 <= Mi <= 50, 0 <= Ai < Mi

Output

For each case output the least positive integer X which Kiki was counting in the sample output format. If there is no solution then output ⑴.

Sample Input

 2
2
14 57
5 56
5
19 54 40 24 80
11 2 36 20 76 

Sample Output

 Case 1: 341
Case 2: 5996 

先可以先找两个同余方程设通解为N；

N=r1(mod(m1)),N=r2(mod(m2))；

明显可以化为k1*m1+r1=k2*m2+r2;--->k1*m1+(-k2*m2)=r2-r1;

设a=m1,b=m2,x=k1,y=(-k2),c=r2-r1方程可写为ax+by=c;

由欧几里得解得x便可,那末将x化为原方程的最小正整数解，(x*(c/d)%(b/d)+(b/d))%(b/d);

这里看不懂的去看解模线性方程。那末这个x就是原方程的最小整数解。

所以N=a*（x+n*（b/d））+r1====N=(a*b/d)*n+(a*x+r1),

这里只有n为未知数所以又是1个N=(a*x+r1)(mod(a*b/d))的式子，

然后只要不断的将两个式变成1个式子，最后就可以解出这个方程组的解。

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3579

转载请注明出处：寻觅&星空の孩子
孩子的专栏

#include<stdio.h> #define LL __int64 void exgcd(LL a,LL b,LL& d,LL& x,LL& y) { if(!b){d=a;x=1;y=0;} else { exgcd(b,a%b,d,y,x); y-=x*(a/b); } } LL gcd(LL a,LL b) { if(!b){return a;} gcd(b,a%b); } LL M[55],A[55]; LL China(int r) { LL dm,i,a,b,x,y,d; LL c,c1,c2; a=M[0]; c1=A[0]; for(i=1; i<r; i++) { b=M[i]; c2=A[i]; exgcd(a,b,d,x,y); c=c2-c1; if(c%d) return ⑴;//c1定是d的倍数，如果不是，则，肯定无解 dm=b/d; x=((x*(c/d))%dm+dm)%dm;//保证x为最小正数//c/dm是余数，系数扩大余数被 c1=a*x+c1; a=a*dm; } if(c1==0)//余数为0，说明M[]是等比数列。且余数都为0 { c1=1; for(i=0;i<r;i++) c1=c1*M[i]/gcd(c1,M[i]); } return c1; } int main() { int T,n,t=0; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%I64d",&M[i]); } for(int i=0;i<n;i++) { scanf("%I64d",&A[i]); } LL ans=China(n); printf("Case %d: %I64d ",++t,ans); } return 0; } /* 20 2 14 57 5 56 5 19 54 40 24 80 11 2 36 20 76 2 14 57 5 56 2 19 54 11 2 */

------分隔线----------------------------