HDU 1573 中國剩余定理 + 不互質(zhì)

2019-11-08 02:42:25

字體：大中小

供稿：網(wǎng)友

HDU 1573

鏈接： HDU 1573

題解

中國剩余定理不互質(zhì) 兩兩合并：先可以先找兩個同余方程設通解為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化為原方程的最小正整數(shù)解，(x*(c/d)%(b/d)+(b/d))%(b/d); 這里看不懂的去看解模線性方程。那么這個x就是原方程的最小整數(shù)解。所以N=a*（x+n*（b/d））+r1====N=(a*b/d)*n+(a*x+r1), 這里只有n為未知數(shù)所以又是一個N=(a*x+r1)(mod(a*b/d))的式子，然后只要不斷的將兩個式變成一個式子，最后就能解出這個方程組的解。

code

/** *@author : adrui *///package adrui;import java.util.*;import static java.lang.System.*;public class Main { public static void main(String...args){ Scanner in = new Scanner(System.in); long t = in.nextLong(); long[] mod = new long[15]; long[] left = new long[15]; while(t-- > 0){ long N = in.nextLong(), n = in.nextLong(); for(int i = 1; i <= n; ++i) mod[i] = in.nextLong(); for(int i = 1; i <= n; ++i) left[i] = in.nextLong(); long modNum = mod[1], leftNum = left[1]; long[] x = new long[1]; long[] y = new long[1]; boolean f = true; for(int i = 2; i <= n; ++i){ long gcd = expgcd(modNum, mod[i], x, y); long c = left[i] - leftNum; if(c % gcd != 0){f = false; break;}/**判斷是否有解*/ x[0] *= c / gcd; long t1 = modNum, t2 = mod[i] / gcd; x[0] = (x[0] % t2 + t2) % t2; modNum = t1 * t2;//模數(shù) leftNum = ((leftNum + t1 * x[0]) % modNum + modNum) % modNum;//余數(shù)合并 } long ans = 0; if(f){ if(leftNum <= N) ++ans; ans += (N - leftNum) / modNum; if(leftNum == 0) --ans;/**排0...*/ } out.PRintln(ans); } in.close(); } public static long expgcd(long a, long b, long[] x, long[] y) { if(b == 0){ x[0] = 1; y[0] = 0; return a; } long d = expgcd(b, a % b, y, x); y[0] -= a / b * x[0]; return d; }}

上一篇：算典03_習題_11_UVA-1588

下一篇：hdu 1241