同余方程组

本文主要是介绍同余方程组，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

由上可得两个同余方程可得一个线性方程 ，linearEquation（m1，-m2，a2-a1） 可解出y1

代回x=a1+m1y1，得：x0=a1+m1y1 ==> x=x0+k*min(m1,m2),得一个新方程：

x=x0(mod min(m1,m2))

此处涉及的是逐级合并法，最终的x的结果为上一个x关于最后两式子的m的最小公倍数的同余方程，即x=x0(mod min(m（n-1）,m(n)))

以POJ-1006生理周期为例题

题目描述

人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。

输入
输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并且小于365, 所求的时间小于21252。

当p = e = i = d = -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

输出：case1: the next tirple peak occurs in 21252 days

         case2: the next tirple peak occurs in 21152 days

         case3: the next tirple peak occurs in 19575 days

         case4: the next tirple peak occurs in 16994 days

         case5: the next tirple peak occurs in 8910 days

         case6: the next tirple peak occurs in 10789 days

思路：

周期固定：23，28，33。依照题意有：d1+23*k1=x                 k是一个倍数

                                                         d2+28*k2=x        不难发现这其实是一组同余方程组 

                                                         d3+33*k3=x 

依照上文可将其化为:x≡d1%23

                               x≡d2%28

                               x≡d3%33

此时可以将d1、d2、d3看为一个a数组；23、28、33看为数组m；将其传入方法

linearEquationGroup(a,m)中。

不过需要注意的是这里所求的时间是：x-d。

有因为题意要求所求的时间小于21252，并且 所有给定时间（d）是非负的并且小于365。有可能x在d的前面（假如d为300，往后过了一段日子到了第二年的某天达到要求，此时x是处于d的前面，即x<d）所以当x<d时需要先将x加上21252

代码实现如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class POJ1006Biorhythms {
    public static void main(String[] args) throws Exception{
        Scanner sc=new Scanner(System.in);
        int t=1;
        List<long[]> aList=new ArrayList<long[]>();
        List<Long> dList=new ArrayList<Long>();
        while (sc.hasNext()){
            long[] a={sc.nextLong(),sc.nextLong(),sc.nextLong()};
            long d=sc.nextLong();
            if (a[0]==-1 && a[1]==-1 && a[2]== -1 && d==-1){
                break;
            }else {
                aList.add(a);
                dList.add(d);
            }
        }
        for (int i=0;i<aList.size();i++){
            long[] a=aList.get(i);
            long d=dList.get(i);
            long[] m={23,28,33};
            long res=ExtGcd.linearEquationGroup(a,m);
            while (res<=d){
                res+=21252;
            }
            System.out.println("Case"+(t++)+": he next tirple peak occurs in "+(res-d)+" days");
        }
    }
    private static class ExtGcd {
        static long x;
        static long y;

        /*调用完成后x y是ax+by=gcd（a，b）的解*/
        public static long ext_gcd(long a, long b) {
            if (b == 0) {
                x = 1;
                y = 0;
                return a;
            }
            long res = ext_gcd(b, a % b);
            long x1 = x;
            x = y;
            y = x1 - a / b * y;
            return res;
        }

        /**
         * 线性方程
         * ax+by=m 当m是gcd（a，b）倍数时有解
         * 等价于ax=m mod b
         */
        public static long linearEquation(long a, long b, long m) throws Exception {
            long d = ext_gcd(a, b);
            //m不是gcd（a，b）的倍数，这个方程无解
            if(m % d!=0)throw new Exception("无解");
            long n = m / d;
            x *= n;
            y *= n;
            return d;
        }
        /**
         *求线性同余方程组
         *x=a1(%m1)
         * =a2(%m2)
         * =a3(%m3)
         *x=a1+m1y1
         *x=a2+m2y2
         *==>m1y1-m2y2=a2-a1 这是一个线性方程，可解出y1 linearEquation（m1，-m2，a2-a1）
         *代回x=a1+m1y1，得：x0=a1+m1y1 --> x=x0+k*min(m1,m2),得一个新方程：
         *x=x0(mod min(m1,m2))
         */
        public static long linearEquationGroup(long[] a,long[] m)throws Exception{
            int len=a.length;
            if(len == 0 && a[0] == 0){
                return m[0];
            }
            for(int i=1;i<len;i++){
                //这里往前看是两个方程
                long a2_a1=a[i]-a[i-1];
                long d=linearEquation(m[i-1],-m[i],a2_a1);
                //现在的x是y1，用y1求得一个特解
                long x0=a[i-1]+m[i-1]*x;
                long min=m[i-1]*m[i]/d;
                a[i]=(x0%min+min)%min;//x0变成正数
                m[i]=min;
            }
            //合并完成之后，只有一个方程：x=a[len](%m[len])
            //long d=linearEquation(1,m[len-1],a[len-1]);
            return a[len-1]%m[len-1];
        }
    }
}

这篇关于同余方程组的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！