【題目大意】：求在小于等于N的正整數(shù)中有多少個X滿足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)，

HDU 1573 X問題 （中國剩余定理）

    【思路】中國剩余定理的應(yīng)用，注意是求滿足一定條件的個數(shù)

    代碼：

/** Problem: HDU No.1573* Running time: 0MS* Complier: G++* Author: javaherongwei* Create Time:  10:39 2015/9/19 星期六* 中國剩余定理的特殊情況：ai不一定相互互質(zhì)*/#include<stdio.h>#include<string.h>#include<iostream>#include using namespace std;typedef long long LL;const int N=15;LL a[N],b[N];LL n,m,ans,m1,r1,m2,r2,c,x,t;bool ok;int tt;void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y){/// a*x+b*y=gcd(a,b)=d;(x,y) 為其一組整數(shù)解    if(!b){        d=a,x=1,y=0;    }    else{        ex_gcd(b,a%b,d,y,x);        y-=x*(a/b);    }}LL ex_crt(LL *a,LL *b,LL n){    LL x,y,d;    m1=a[0],r1=b[0];    for(int i=1; i<m; ans="(n-r1)/m1+1;///m1為ai的最小公倍數(shù)，凡是m1*i+r1的都是符合要求的數(shù)，其中r1最小" c="r2-r1;" i="0;" int="" lld="" m="m1*x%m+M(i-1)%m=M(i-1)%m=r" m1="m1*m2/d;" m2="a[i];" m2y="c=r2-r1,若(x0,y0)是一組整數(shù)解,那么(x0+k*m2/d,y0-k*m1/d)也是一組整數(shù)解(k為任意整數(shù))" mi="m1*x+M(i-1)=r2-m2*y(m1為前i個m的最小公倍數(shù));對m2取余時，余數(shù)為r2；" k="1;" pre="" r1="=0)" r2="b[i];" return="" t="m2/d;" x="(c/d*x%t+t)%t;///保證x0是正數(shù)，因為x+k*t是解，(x%t+t)%t也必定是正數(shù)解(必定存在某個k使得(x%t+t)%t=x+k*t)" x0="x*c/d,y0=x*c/d;" y="c，如果c不是d的倍數(shù)就無整數(shù)解"></p></m;></iostream></string.h></stdio.h>