专栏首页机器学习入门挑战程序竞赛系列(41):4.1中国剩余定理

挑战程序竞赛系列(41):4.1中国剩余定理

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/77717764

挑战程序竞赛系列(41):4.1中国剩余定理

详细代码可以fork下Github上leetcode项目,不定期更新。

练习题如下:

POJ 1006: Biorhythms

今天学习了下中国剩余定理,很多参考资料啊,推荐博文: http://blog.csdn.net/acdreamers/article/details/8050018

其他的可看可不看,简单来说,中国剩余定理是用来求解同余方程组的,比如

x≡1mod5x≡2mod6x≡3mod7

x \equiv 1 \mod 5 \\ x \equiv 2 \mod 6 \\ x \equiv 3 \mod 7 \\

中国剩余定理指出,如果给出的每个方程模数两两互素,就能通过一种方法计算出来,具体方法可以参考《初等数论及其应用》。

在这里给出书上的证明:

该证明还是很好理解的,主要还是通过两两互素的性质构造一个联立解,最后证明联立解符合每个方程即可,给人一种凑答案的过程,此解法如何想到令人深思。

具体做法如下:

好了,有了这些知识,第一题能解了,无非把上述思想用代码实现一遍。

代码如下:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main{

    String INPUT = "./data/judge/201708/P1006.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    void solve() {
        int t = 0;
        while (true){
            int p = ni();
            int e = ni();
            int i = ni();
            int d = ni();
            if (p == -1 && e == -1 && i == -1 && d == -1) break;
            int[] a = new int[3];
            int[] m = new int[3];
            a[0] = p;
            a[1] = e;
            a[2] = i;
            m[0] = 23;
            m[1] = 28;
            m[2] = 33;
            int ans = CRT(a, m, 3);
            if (ans <= d){
                ans += 21252;
            }
            out.println("Case " + (++t) + ": the next triple peak occurs in " + (ans - d) + " days.");
        }
    }

    class Pair{
        int d;
        int x;
        int y;
        public Pair(int d, int x, int y){
            this.d = d;
            this.x = x;
            this.y = y;
        }
    }

    public Pair extgcd(int a, int b){
        if (b == 0){
            return new Pair(a, 1, 0);
        }
        else{
            Pair p = extgcd(b, a % b);
            Pair ans = new Pair(0, 0, 0);
            ans.d = p.d;
            ans.x = p.y;
            ans.y = p.x - (a / b) * p.y;
            return ans;
        }
    }

    public int mod_inverse(int a, int m){
        Pair p = extgcd(a, m);
        if (p.d != 1) return -1;
        return (p.x % m + m) % m;
    }

    public int CRT(int[] a, int[] m, int n){
        int M = 1;
        int ans = 0;
        for (int i = 0; i < n; ++i){
            M *= m[i];
        }
        for (int i = 0; i < n; ++i){
            int inv = mod_inverse(M / m[i], m[i]);
            ans += a[i] * M / m[i] * inv;
            ans %= M;
        }
        return ans;
    }


    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!oj){
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more(){
        return in.hasNext();
    }

    public int ni(){
        return in.nextInt();
    }

    public long nl(){
        return in.nextLong();
    }

    public double nd(){
        return in.nextDouble();
    }

    public String ns(){
        return in.nextString();
    }

    public char nc(){
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;
        public boolean hasNext(){
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}

POJ 2891: Strange Way to Express Integers

嘿,中国剩余定理表明同余方程组两两互素的情况下可解,那么遇到模数不互素的情况该如何?

参考博文:http://www.cnblogs.com/MashiroSky/p/5918158.html

此篇讲的还是比较详细的,尤其这文字解释令人一下豁然开朗,我就不重复劳动力了。

但个人总觉得吧,这和中国剩余定理没啥关系了吧,难道这种解法也是孙子发明的?

大致思路是对所有同余方程两两合并,在合并的过程中可以求出新的一个特解和它的一个解集,解集用新的同余方程表示(这想法相当漂亮),那么该解集就能慢慢适应所有同余方程了。

最终在解集中找寻一个最小的即可,上述两篇博文有C++的具体实现,Java版本的就自己补上吧。

代码如下:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main{

    String INPUT = "./data/judge/201708/P2891.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    void solve() {
        while (more()){
            int n = ni();
            long[] a = new long[n];
            long[] m = new long[n];
            for (int i = 0; i < n; ++i){
                m[i] = ni();
                a[i] = ni();
            }
            out.println(CRT(a, m, n));
        }
    }

    class GCD{
        long d;
        long x;
        long y;

        public GCD(long d, long x, long y){
            this.d = d;
            this.x = x;
            this.y = y;
        }
    }

    public long gcd(long a, long b){
        if (b == 0) return a;
        else return gcd(b, a % b);
    }

    public GCD extgcd(long a, long b){
        if (b == 0) return new GCD(a, 1, 0);
        else{
            GCD g   = extgcd(b, a % b);
            GCD ans = new GCD(0, 0, 0);
            ans.d = g.d;
            ans.x = g.y;
            ans.y = g.x - (a / b) * g.y;
            return ans;
        }
    }

    public long mod_inverse(long a, long m){
        GCD g = extgcd(a, m);
        if (g.d != 1) return -1;
        return (g.x % m + m) % m;
    }

    class LL{
        long val;

        public LL(){}

        public LL(long val){
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

    public boolean merge(long a1, long m1, long a2, long m2, LL a3, LL m3){
        GCD g = extgcd(m1, m2);
        long c = a2 - a1;
        long d = g.d;
        if (c % d != 0) return false;
        m1 /= d;
        m2 /= d;
        c  /= d;
        long inv = mod_inverse(m1, m2);
        c *= inv;
        c %=  m2;
        c *= m1 * d;
        c += a1;
        m3.val = m1 * m2 * d;
        a3.val = c;
        return true;
    }

    public long CRT(long[] a, long[] m, int n){
        long a1 = a[0];
        long m1 = m[0];
        for (int i = 1; i < n; ++i){
            long a2 = a[i];
            long m2 = m[i];

            LL a3 = new LL();
            LL m3 = new LL();
            if (!merge(a1, m1, a2, m2, a3, m3)) return -1;

            a1 = a3.val;
            m1 = m3.val;
        }
        return (a1 % m1 + m1) % m1;
    }



    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!oj){
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more(){
        return in.hasNext();
    }

    public int ni(){
        return in.nextInt();
    }

    public long nl(){
        return in.nextLong();
    }

    public double nd(){
        return in.nextDouble();
    }

    public String ns(){
        return in.nextString();
    }

    public char nc(){
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;
        public boolean hasNext(){
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}

POJ 3708: Recurrent Function

此题对数学的要求较高,还是有一定难度的,用到的知识点也较多,简单说说我的心路历程吧。

就拿式子:

f(d×n+j)=d×f(n)+bj

f (d \times n + j) = d \times f(n) + b_j 你能想到什么?它实际上是一种m转d进制,这是思维上的突破,想到这点后续都简单了。

我们可以把递推式化为最终的表达式如下:

f(m)=ap1⋅dn−1+∑i=2n(bpi⋅dn−i),ap1ϵ[1,d),(bpiϵ[0,d),iϵ[2,n)]

f(m) = a_{p_1} \cdot d ^{n - 1} + \sum_{i=2}^n( {b_{p_i}}\cdot d ^{n - i}) , a_{p_1}\epsilon[1,d), (b_{p_i}\epsilon[0, d),i\epsilon[2, n)]

如果递推式难以理解的话,你可以想象10进制转d进制的一个过程,因为递推式其实模拟的就是这个过程,并且在转换的过程当中,余数一一对应到了bjb_j上了。

当然你也可以参考《具体数学》P16,它也介绍了一些,此处推荐博文: http://www.hankcs.com/program/algorithm/poj-3708-recurrent-function.html 但代码量相对冗长,比较难懂。

好了,m转成d进制,对应的值f(m)=(ap1bp2...bpn)df(m) = (a_{p_1}b_{p_2}...b_{p_n})_d

所以第一步判断m和k转到d进制后,位数是否相等,不相等则无解。

接着,我们要考虑m中每一位的变化了, 因为经过一次f映射,实际上是从set中找一个数置换,而set中的值是有限个数,且在[1, d)之间,那么必然在置换过程中会存在循环的情况,那么自然的就考虑m中的每一位经过多少次能将mim_i置换到kik_i上去。

这样就可以列出一系列的同余方程了。

此处可以参考博文: http://blog.csdn.net/adjky/article/details/60583393 思路很清楚,代码很精简。

代码如下:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{

    String INPUT = "./data/judge/201708/P3708.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    int[] A;
    int[] B;

    void solve() {
        while (true){
            int N = ni();

            if (N == -1) break;

            A = new int[N];
            B = new int[N];

            for (int i = 1; i < N; ++i){
                A[i] = ni();
            }

            for (int i = 0; i < N; ++i){
                B[i] = ni();
            }
            String m = ns();
            String k = ns();

            int[] nm = new int[m.length() + 16];
            for (int i = m.length() - 1; i >= 0; --i) nm[i] = m.charAt(i) - '0';
            int[] nk = new int[k.length() + 16];
            for (int i = k.length() - 1; i >= 0; --i) nk[i] = k.charAt(i) - '0';

            LEN_M = tran(nm, m.length(), M, N);
            LEN_K = tran(nk, k.length(), K, N);


            //radix(m, k, N);
            if (LEN_M != LEN_K) out.println("NO");
            else{
                getRC(LEN_M);
                boolean valid = true;
                for (int i = 0; i < LEN_M; ++i){
                    if (C[i] == -1){
                        valid = false;
                        break;
                    }
                }
                if (!valid) out.println("NO");
                else{
                    long ans = CRT(C, R, LEN_M);
                    if (ans == -1) out.println("NO");
                    else{
                        out.println(ans);
                    }
                }
            }
        }
    }

    /********************欧几里德两两合并***************************/
    class GCD{
        long d;
        long x;
        long y;

        public GCD(long d, long x, long y){
            this.d = d;
            this.x = x;
            this.y = y;
        }
    }

    public long gcd(long a, long b){
        if (b == 0) return a;
        else return gcd(b, a % b);
    }

    public GCD extgcd(long a, long b){
        if (b == 0) return new GCD(a, 1, 0);
        else{
            GCD g   = extgcd(b, a % b);
            GCD ans = new GCD(0, 0, 0);
            ans.d = g.d;
            ans.x = g.y;
            ans.y = g.x - (a / b) * g.y;
            return ans;
        }
    }

    public long mod_inverse(long a, long m){
        GCD g = extgcd(a, m);
        if (g.d != 1) return -1;
        return (g.x % m + m) % m;
    }

    class LL{
        long val;

        public LL(){}

        public LL(long val){
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

    public boolean merge(long a1, long m1, long a2, long m2, LL a3, LL m3){
        GCD g = extgcd(m1, m2);
        long c = a2 - a1;
        long d = g.d;
        if (c % d != 0) return false;
        m1 /= d;
        m2 /= d;
        c  /= d;
        long inv = mod_inverse(m1, m2);
        c *= inv;
        c %=  m2;
        c *= m1 * d;
        c += a1;
        m3.val = m1 * m2 * d;
        a3.val = c;
        return true;
    }

    public long CRT(int[] a, int[] m, int n){
        long a1 = a[0];
        long m1 = m[0];
        for (int i = 1; i < n; ++i){
            long a2 = a[i];
            long m2 = m[i];

            LL a3 = new LL();
            LL m3 = new LL();
            if (!merge(a1, m1, a2, m2, a3, m3)) return -1;

            a1 = a3.val;
            m1 = m3.val;
        }
        return (a1 % m1 + m1) % m1;
    }

    /****************大数进制转换****************/
    int MAX_D = 500 + 16;
    int[] M = new int[MAX_D];
    int[] K = new int[MAX_D];
    int LEN_M;
    int LEN_K;

    public int tran(int ten[], int len, int ans[], int d){
        int cnt = 0;
        int tcnt = 0;
        while(tcnt < len){

            for(int i = tcnt; i < len; ++i){
                ten[i + 1] += (ten[i] % d) * 10;
                ten[i] /= d;
            }/**模拟除法,余数 * 10存在ten[len]中*/

            ans[cnt++] = ten[len] / 10;
            ten[len] = 0;
            while(ten[tcnt] == 0 && tcnt < len) ++tcnt;
        }
        return cnt;
    }

    /***************************计算每一位的模数****************************/
    int[] R = new int[MAX_D];
    int[] C = new int[MAX_D];

    // 获得模数
    public void getRC(int len){
        Arrays.fill(C, -1);
        int id = len - 1;
        R[id] = 1;
        int cnt = 0;
        if (M[id] == K[id]) C[id] = 0;
        for (int i = A[M[id]]; i != M[id]; i = A[i]){
            ++R[id];
            ++cnt;
            if (i == K[id]) C[id] = cnt;
        }

        for (int i = 0; i < id; ++i){
            if (K[i] == M[i]) C[i] = 0;
            R[i] = 1;
            cnt  = 0;
            for (int j = B[M[i]]; j != M[i]; j = B[j]){
                ++R[i];
                ++cnt;
                if (K[i] == j) C[i] = cnt;
            }
        }
    }

    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!oj){
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more(){
        return in.hasNext();
    }

    public int ni(){
        return in.nextInt();
    }

    public long nl(){
        return in.nextLong();
    }

    public double nd(){
        return in.nextDouble();
    }

    public String ns(){
        return in.nextString();
    }

    public char nc(){
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;
        public boolean hasNext(){
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}

注意m和k是大数,用字符串去取,且需要用大数高精度转d进制的做法,才能AC。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode Weekly Contest 29解题思路

    代码很简单,简单说明下思路就出来了。按照题意,不管怎么二分,整个数组都会被划分成两部分和,这两部分和必然一大一小。如nums = [1,4,3,2],划分如下[...

    用户1147447
  • 挑战程序竞赛系列(74):4.3强连通分量分解(1)

    挑战程序竞赛系列(74):4.3强连通分量分解(1) 传送门:POJ 2186: Popular Cows 题意: 每头牛都想成为牛群中的红人。给定N头牛的牛...

    用户1147447
  • 挑战程序竞赛系列(70):4.7后缀数组(2)

    挑战程序竞赛系列(70):4.7后缀数组(2) 传送门:POJ 1509: Glass Beads 题意: The description of the ne...

    用户1147447
  • 10个常见的 Java 错误及避免方法之第二集(后续持续发布)

    当程序缺少关闭大括号(“}”)时,Java代码中就会发生此错误消息。 有时我们可以通过在代码的末尾放置大括号来快速修复错误。

    用户1289394
  • LeetCode Weekly Contest 29解题思路

    代码很简单,简单说明下思路就出来了。按照题意,不管怎么二分,整个数组都会被划分成两部分和,这两部分和必然一大一小。如nums = [1,4,3,2],划分如下[...

    用户1147447
  • LeetCode 441. 排列硬币(数学解方程)

    你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。

    Michael阿明
  • Java能写外挂吗?那就写个跳一跳辅助程序吧

    ##起初是想使用按键精灵脚本程序控制,但还是选择熟悉的java。我这里使用了工具,造成延迟问题。也求教:java控制安卓的正确姿势,

    三哥
  • 挑战程序竞赛系列(94):3.6凸包(5)

    挑战程序竞赛系列(94):3.6凸包(5) 传送门:POJ 2079: Triangle 题意: 求三个点构成的最大三角形面积。 思路: 可以证明,三点构...

    用户1147447
  • 挑战程序竞赛系列(91):3.6凸包(2)

    挑战程序竞赛系列(91):3.6凸包(2) 传送门:POJ 1113: Wall 题意参考hankcs: http://www.hankcs.com/pro...

    用户1147447
  • 挑战程序竞赛系列(90):3.6凸包(1)

    挑战程序竞赛系列(90):3.6凸包(1) 传送门:POJ 2187: Beauty Contest 题意: 平面上有N个牧场。i号牧场的位置在格点(xi,y...

    用户1147447

扫码关注云+社区

领取腾讯云代金券