首页 > 代码库 > 中国剩余定理小结 (互质,非互质) (poj 1006,hdu 3579)

中国剩余定理小结 (互质,非互质) (poj 1006,hdu 3579)

2024-11-23 20:51:38   203人阅读

中国剩余定理小结 (互质,非互质) (poj 1006,hdu 3579)

先证明下中国剩余定理

条件：
x%m_1=a_1
x%m_2=a_2
...
x%m_n=a_n
m_1,m_2,...,m_n两两互质

证明：
设M=m_1*m_2*m_3*...*m_n
M_i=M/m_i
因为gcd(M_i,m_i)=1，所以M_ix+m_iy=1
(t_i*M_i)%m_i=1 //由Ext_gcd(M_i,m_i,x,y)求出,t_i=x
方程组的解：x=a_1*t_1*M_1+...+a_n*t_n*M_n


题目：poj 1006

http://poj.org/problem?id=1006

题意：
现在有三条式子：
x%23=a1
x%28=a2
x%33=a3
现在求最小的整数(x-d)
限制：
0 <= d <= 365


 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*poj 1006
  题意：
  现在有三条式子：
  x%23=a1
  x%28=a2
  x%33=a3
  现在求最小的整数(x-d)
  限制：
  0 <= d <= 365
  思路：
  中国剩余定理

  条件：
  x%m_1=a_1
  x%m_2=a_2
  ...
  x%m_n=a_n
  m_1,m_2,...,m_n两两互质
  证明：
  设M=m_1*m_2*m_3*...*m_n
  M_i=M/m_i
  因为gcd(M_i,m_i)=1，所以M_ix+m_iy=1
  (t_i*M_i)%m_i=1   //由Ext_gcd(M_i,m_i,x,y)求出,t_i=x
  方程组的解：x=a_1*t_1*M_1+...+a_n*t_n*M_n
 */
#include<iostream>
#include<cstdio>
using namespace std;
#define LL __int64
LL Ext_gcd(LL a,LL b,LL &x,LL &y){
    if(b==0) { x=1, y=0; return a; }
    LL ret=Ext_gcd(b,a%b,y,x);
    y-=a/b*x;
    return ret;
}
LL CRT(LL a[],LL m[],int n){
    LL M=1;
    for(int i=0;i<n;++i) M*=m[i];
    LL ret=0;
    for(int i=0;i<n;++i){
        LL x,y;
        LL tm=M/m[i];
        Ext_gcd(tm,m[i],x,y);
        ret=(ret+tm*x*a[i])%M;
    }
    return (ret+M)%M;
}
int main(){
    LL a[3],m[3],d;
    m[0]=23,m[1]=28,m[2]=33;
    LL M=m[0]*m[1]*m[2];
    int cas=0;
    while(scanf("%I64d%I64d%I64d%I64d",&a[0],&a[1],&a[2],&d)){
        if(a[0]==-1 && a[1]==-1 && a[2]==-1 && d==-1) break;
        LL ans;
        ans=CRT(a,m,3)-d;
        if(ans==0) ans=M;
        else ans=(ans+M)%M;
        printf("Case %d: the next triple peak occurs in %I64d days.\n",++cas,ans);
    }
    return 0;
}


在说下非互质情况下的中国剩余定理

证明如下：

由于不两两互质，所以只能两个两个解。
设通解为N
->N=m1*k1+r1,N=m2*k2+r2
->m1*k1+r1=m2*k2+r2
->k1*m1+(-k2*m2)=r2-r1
->设a=m1,b=m2,x=k1,y=(-k2),c=r2-r1
->ax+by=c 通过 d=Ext_gcd(a,b,x,y) 得 d,x
->最小整数解x=(x*(c/d)%(b/d)+(b/d))%(b/d)
->N=a*(x+n*(b/d))+r1
->N=(a*b/d)*n+(a*x+r1)
->令m3=a*b/d,r3=a*x+r1,k3=n
->N=m3*k3+r3 化成了一个新的式子，不断迭代然后出结果。


题目：hdu 3579

http://acm.hdu.edu.cn/showproblem.php?pid=3579

题意：
给出m_1,m_2,...m_n;a_1,a_2,...,a_n,非互质中国剩余定理。


 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*hdu 3579
  题意：
  给出m_1,m_2,...m_n;a_1,a_2,...,a_n,非互质中国剩余定理。
  思路：
  中国剩余定理

  由于不两两互质，所以只能两个两个解。
  设通解为N
  ->N=m1*k1+r1,N=m2*k2+r2
  ->m1*k1+r1=m2*k2+r2
  ->k1*m1+(-k2*m2)=r2-r1
  ->设a=m1,b=m2,x=k1,y=(-k2),c=r2-r1
  ->ax+by=c 通过 d=Ext_gcd(a,b,x,y) 得 d,x
  ->最小整数解x=(x*(c/d)%(b/d)+(b/d))%(b/d)
  ->N=a*(x+n*(b/d))+r1
  ->N=(a*b/d)*n+(a*x+r1)
  ->令m3=a*b/d,r3=a*x+r1,k3=n
  ->N=m3*k3+r3 化成了一个新的式子，不断迭代然后出结果。
 */
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL __int64
LL Ext_gcd(LL a,LL b,LL &x,LL &y){
    if(b==0){ x=1,y=0; return a; }
    LL ret=Ext_gcd(b,a%b,y,x);
    y-=a/b*x;
    return ret;
}
int n;
LL a[100005],m[100005];
LL CRT(){
    LL M=m[0];
    LL ret=a[0];
    for(int i=1;i<n;++i){
        LL x,y,d;
        d=__gcd(M,m[i]);
        if((a[i]-ret)%d) return -1; //注意无解时的返回值
        Ext_gcd(M,m[i],x,y);
        x=(a[i]-ret)/d*x%(m[i]/d);
        ret+=x*M;
        M=M/d*m[i];
        ret%=M;
    }
    ret=(ret+M)%M;
    return ret==0?M:ret;    //模除类问题要注意答案能不能为0
}
int main(){
    int T;
    int cas=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]);
        printf("Case %d: %I64d\n",++cas,CRT());
    }
    return 0;
}

中国剩余定理小结 (互质,非互质) (poj 1006,hdu 3579)


联系
我们