您當前位置：首頁 > php開源 > php教程 > Hello Kiki（hdu3579+不互質的中國剩余定理）

Hello Kiki（hdu3579+不互質的中國剩余定理）

來源：程序員人生發布時間：2015-05-28 08:38:10 閱讀次數：3164次

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 */

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生

------分隔線----------------------------

上一篇 異或運算

下一篇 VS2015 RC 安裝體驗

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

Hello Kiki（hdu3579+不互質的中國剩余定理）