hdu-1370(中国剩余定理余数互质）&&hdu-1573(中国剩余定理余数不互质)

冷不防 2022-06-10 08:38 181阅读 0赞

中国剩余定理是用来求解一次同余方程组问题的重要方法，是数论的一个重要定理。

对于同余方程组：

x=a1 mod n1

x=a2  mod n2

......................

x=ak  mod nk

我们就可以利用中国剩余定理来求解x!

下面我们分俩种情况来求解：

1  当n1  n2     nk俩俩互质时的情况：

我们由方程组第一个式子可以得到：x1=n1\*k1+a1

同理我们可以得到其他式子:xk=nk\*kk+ak

那么我们构造一个数X=x1+x2+x3+......xk   很明显x1满足第一个式子，xk满足第k个式子，那么我们构造的X是不是满足所有的式子了？

很明显一般情况下肯定不满足，那么有什么条件就一定满足了?

我们把X回带入第一个式子我们得到：X mod n1=a1 即  （x1+x2+x3+....+xk) mod n1=a1

我们可以得到 x1  mod n1 +(x2+x3+......xk) mod n1=a1，也就是说当x2+x3+....xk被n1整除时第一个式子就满足了。

同理我们知道了  当  xt  mod  nt+ (x1+x2+...+xt-1+xt+1+...xk) mod nt=at 满足时 即后面的式子可以被nt整除。

所以我们可以得到如下结论:

x1是除以n1 余a1  但是也是 n2  n3  ...nk的倍数

同理可以得到其他的xt的满足条件。

我们明白了原理，接下来就是代码实现了:

第一个条件 x1是n2  n3  .. nk的倍数：  因为n1到nk 俩俩互质，n2\*n3\*n4\*...\*nk就是它们的最小公倍数

第二个条件  x1 mod  n1=a1 这里我们可以先求出 x mod n1=1的解（扩展欧几里得），然后x1=x\*a\[i\]

代码如下:

int exgcd(int a,int b,int &x,int &y)
    {
        if (b==0) {
            x=1;
            y=0;
            return a;
        }
        int r=exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
        return r;
    }
    int CRT(int *a,int *m,int n)//求解
    {
        int w=1;
        int ans=0;
        for (int i=0;i<n;i++)
            w=w*m[i];
        for (int i=0;i<n;i++) {
            int x,y;
            int mi=w/m[i];//求出最小公倍数
            exgcd(mi,m[i],x,y);
            ans=(ans+mi*x*a[i])%w;
        }
        if (ans<0) ans+=w;
        return ans;
    }

hdu 1370

Problem Description

Some people believe that there are three cycles in a person's life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, and they have periods of lengths 23, 28, and 33 days, respectively. There is one peak in each period of a cycle. At the peak of a cycle, a person performs at his or her best in the corresponding field (physical, emotional or mental). For example, if it is the mental curve, thought processes will be sharper and concentration will be easier.  
  
Since the three cycles have different periods, the peaks of the three cycles generally occur at different times. We would like to determine when a triple peak occurs (the peaks of all three cycles occur in the same day) for any person. For each cycle, you will be given the number of days from the beginning of the current year at which one of its peaks (not necessarily the first) occurs. You will also be given a date expressed as the number of days from the beginning of the current year. You task is to determine the number of days from the given date to the next triple peak. The given date is not counted. For example, if the given date is 10 and the next triple peak occurs on day 12, the answer is 2, not 3. If a triple peak occurs on the given date, you should give the number of days to the next occurrence of a triple peak.  
  
  
This problem contains multiple test cases!  
  
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.  
  
The output format consists of N output blocks. There is a blank line between output blocks.

Input

You will be given a number of cases. The input for each case consists of one line of four integers p, e, i, and d. The values p, e, and i are the number of days from the beginning of the current year at which the physical, emotional, and intellectual cycles peak, respectively. The value d is the given date and may be smaller than any of p, e, or i. All values are non-negative and at most 365, and you may assume that a triple peak will occur within 21252 days of the given date. The end of input is indicated by a line in which p = e = i = d = -1.

Output

For each test case, print the case number followed by a message indicating the number of days to the next triple peak, in the form:

Sample Input

1 0 0 0 0 0 0 0 100 5 20 34 325 4 5 6 7 283 102 23 320 203 301 203 40 -1 -1 -1 -1

Sample Output

Case 1: the next triple peak occurs in 21252 days. Case 2: the next triple peak occurs in 21152 days. Case 3: the next triple peak occurs in 19575 days. Case 4: the next triple peak occurs in 16994 days. Case 5: the next triple peak occurs in 8910 days. Case 6: the next triple peak occurs in 10789 days.

题目就是第一种情况的模板。

#include<iostream>
    #include<cstdio>
    using namespace std;
    
    int a[3]={23,28,33};
    int b[3];
    
    int exgcd(int a,int b,int &x,int &y)
    {
        if (b==0) {
            x=1;
            y=0;
            return a;
        }
        int r=exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
        return r;
    }
    int CRT(int *a,int *m,int n)
    {
        int w=1;
        int ans=0;
        for (int i=0;i<n;i++)
            w=w*m[i];
        for (int i=0;i<n;i++) {
            int x,y;
            int mi=w/m[i];
            exgcd(mi,m[i],x,y);
            ans=(ans+mi*x*a[i])%w;
        }
        if (ans<0) ans+=w;
        return ans;
    }
    int main()
    {
        int t,d,icase;
        scanf("%d",&t);
        while (t--) {
            icase=1;
           while (scanf("%d%d%d%d",&b[0],&b[1],&b[2],&d)!=EOF) {
                if (b[0]==-1&&b[1]==-1&&b[2]==-1&&d==-1) break;
               int ans=CRT(b,a,3);
               ans=ans-d;
               if (ans<=0) ans+=21252;
               printf("Case %d: the next triple peak occurs in %d days.\n",icase++,ans);
           }
        }
    }

中国剩余定理第二种情况（余数不互质）

对于同余方程组：

x=a1 mod n1

x=a2  mod n2

......................

x=ak  mod nk

我们来变形

x=n1\*k1+a1

x=n2\*k2+a2

........

x=nk\*kk+ak

我们联系一二式，我们得到了

n1\*k1+a1=n2\*k2+a2 即    n1\*k1-n2\*k2=a2-a1 这个式子是不是非常熟悉了  ax+by=c

我们就利用这个扩展欧几里得解方程，解出k1,然后我们就得到了一个x=n1\*k1+a1,我们令a1=x,n1为n1  n2的最小公倍数,得到了新的一个方程x =a1  mod n1,继续这样算，直到算完为止。

代码如下

long long CRT(long long a[],long long n[],int num){
        long long n1=n[0],a1=a[0],n2,a2,k1,k2,x0,gcd,c;
        for(int i=1;i<num;i++){
            n2=n[i],a2=a[i];
            c=a2-a1;
            gcd=exgcd(n1,n2,k1,k2);
            if(c%gcd){
                flag=1;
                return 0;
            }
            x0=c/gcd*k1;
            t=n2/gcd; //周期t
            x0=(x0%t+t)%t;
            a1+=n1*x0;//新求的a1就是前i组的解
            n1=n2/gcd*n1;//前面n1*n2*..nk的最小公倍数
        }
    return a1;
    }

hdu 1573

Problem Description

求在小于等于N的正整数中有多少个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)。

Input

输入数据的第一行为一个正整数T，表示有T组测试数据。每组测试数据的第一行为两个正整数N，M (0 < N <= 1000,000,000 , 0 < M <= 10)，表示X小于等于N，数组a和b中各有M个元素。接下来两行，每行各有M个正整数，分别为a和b中的元素。

Output

对应每一组输入，在独立一行中输出一个正整数，表示满足条件的X的个数。

Sample Input

3 10 3 1 2 3 0 1 2 100 7 3 4 5 6 7 8 9 1 2 3 4 5 6 7 10000 10 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9

Sample Output

1 0 3

也是模板题目:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #define ll long long
    using namespace std;
    
    ll n[15],a[15];
    ll w;
    
    ll exgcd(ll a,ll b,ll &x,ll &y)
    {
        if (b==0) {
            x=1;
            y=0;
            return a;
        }
        ll r=exgcd(b,a%b,x,y);
        ll t=x;
        x=y;
        y=t-a/b*y;
        return r;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while (t--) {
            int nn,m;
            scanf("%d%d",&nn,&m);
            for (int i=0;i<m;i++)
                scanf("%lld",&n[i]);
            for (int i=0;i<m;i++)
                scanf("%lld",&a[i]);
            int flag=0;
            ll a1=a[0],n1=n[0],a2,n2,k1,k2,x0;
            for (int i=1;i<m;i++) {
                a2=a[i],n2=n[i];
                ll c=a2-a1;
                ll gcd=exgcd(n1,n2,k1,k2);
                if (c%gcd) {
                    flag=1;
                    break;
                }
                x0=c/gcd*k1;
                ll t=(n2/gcd);
                x0=(x0%t+t)%t;
                a1+=(n1*x0);
                n1=n1*n2/gcd;
            }
            if (flag||nn<a1) {
                printf("%d\n",0);
            }
            else {
                int res=(nn-a1)/n1+1;
                if (a1==0) res--;//注意求个数就行了
                printf("%d\n",res);
            }
    
        }
        return 0;
    }