挑战程序竞赛系列(13):2.6辗转相除法

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

挑战程序竞赛系列(13):2.6辗转相除法

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

练习题如下:

AOJ 0005: GCD AND LCM

辗转相除法,著名欧几里德算法。

代码如下:

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        long a,b;

        while((str=br.readLine()) != null){
            a = Long.parseLong(str.substring(0, str.indexOf(" ")));
            b = Long.parseLong(str.substring(str.indexOf(" ")+1, str.length()));

            System.out.println(gcd(a, b) + " " + lcm(a,b));

        }
    }

    private static long gcd(long a, long b){
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    private static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

POJ 2429: GCD & LCM Inverse

这道题是我学算法以来,程序代码最长的一次,思路是相当简单的,但为了避免TLE,算法优化不简单。

思路:

  • 取lcm/gcd,如3,60,得到20,在20中找到所有因子,如:2*10,4*5,取因子之和最小的两个因子。
  • 输出 gcd * f1 和 gcd *f2

非常暴力的做法,求因子可以使用试除法,把每个小于num的因子扫描一遍,但时间复杂度为O(n)O(n),当num非常大时,这种时间开销受不了。

两种经典算法,Miller-Rabin素数测试和Pollard_Rho_因数分解算法实现,高级高级,理解起来费劲,尤其是理论推导它为何能够奏效。

学完两种算法后,发现Pollard_Rho也能检测素数,但速度要比Miller-Rabin慢,所以还是用Pollard_Rho做因数分解吧。

代码如下:

    static class Pair{
        long fir;
        long sec;
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        while (true){
            long gcd = in.nextLong();
            long lcm = in.nextLong();
            if (gcd == 0 && lcm == 0) break;
            map = new HashMap<>();
            Pair p = solve(gcd, lcm);
            System.out.println(p.fir * gcd + " " + p.sec * gcd);
        }
    }

    private static Pair solve(long a, long b){
        long c = b / a;
        find(c, 26632);

        int size = 0;
        for (long key : map.keySet()){
            size += map.get(key);
        }

        long[] factor = new long[size];
        int k = 0;
        for (long key : map.keySet()){
            int cnt = map.get(key);
            while ((cnt--) != 0){
                factor[k++] = key;
            }
        }

        int mask = 1 << size;
        long min = Integer.MAX_VALUE;
        Pair p = new Pair();
        for (int i = mask - 1; i>= 0; --i){
            long f1 = 1;
            for (int j = 0, m = 1; j < size; ++j, m <<= 1){
                if ((i & m) != 0){
                    f1 *= factor[j];
                }
            }
            long f2 = c / f1;
            if (f1 < f2 && (f1 + f2) < min){
                p.fir = f1;
                p.sec = f2;
                min = f1 + f2;
            }
        }
        return p;
    }

    public static long quickMul(long a, long b, long mod){
        long ans = 0;
        while (b != 0){
            if ((b & 1) != 0){
                b--;
                ans = (ans + a) % mod;
            }
            b >>= 1;
            a = (a + a) % mod;
        }
        return ans;
    }

    public static long quickPow(long a, long b, long mod){
        long ans = 1;
        while (b != 0){
            if ((b & 1) != 0){
                b--;
                ans = quickMul(ans, a, mod);
            }
            b >>= 1;
            a = quickMul(a, a, mod);
        }
        return ans;
    }

    public static boolean witness(long a, long n){
        long tem = n - 1;
        int j = 0;
        while (tem % 2 == 0){
            tem /= 2;
            j++;
        }
        long x = quickPow(a, tem, n);
        if (x == 1 || x == n - 1) return true;

        while ((j--) != 0){
            x = quickMul(x, x, n);
            if (x == n - 1) return true;
        }
        return false;
    }

    private static long random(long n){
        return Math.abs(new Random().nextLong() % (n + 1));
    }

    public static boolean millerRabin(long n, int times){
        if (n == 2) return true;
        if (n < 2 || n % 2 == 0) return false;

        for (int i = 0; i < times; ++i){
            long a = random(n - 2) + 1;
            if (!witness(a, n)) return false;
        }
        return true;
    }

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

    public static long pollardRho(long n, long c){
        long x, y, d, i = 1, k = 2;
        x = random(n - 1) + 1; //[1,n]
        y = x;
        while (true){
            i++;
            x = (quickMul(x, x, n) + c) % n;
            d = gcd(y - x, n);
            if (1 < d && d < n) return d;
            if (y == x) return n;
            if (i == k){
                y = x;
                k <<= 1;
            }
        }
    }

    static Map<Long, Integer> map;
    public static void find(long n, long c){
        if (n == 1) return;
        if (millerRabin(n, 20)){
            //map.put(n, map.getOrDefault(n, 0) + 1);
            if (!map.containsKey(n)) map.put(n, 0);
            map.put(n, map.get(n) + 1);
            return;
        }
        long p = n;
        long k = c;
        while (p >= n) p = pollardRho(p, c--);
        find(p, k);
        find(n / p, k);
    }

测试了一些基础样例,能通过,但不知道为什么在OJ上提交时,Runtime Error,看不到测试数据,有点蛋疼。

这两篇文章把整个算法的核心讲清楚了,主要用到了费马小定理,以及一些素数合数的基本性质。

在这里,讲一些帮助理解算法和解决问题的感悟吧,自己能够在适当时候想起来就算没白分析。

快速乘法&&快速幂

我并不知道乘法变成加法的形式,到底是代码层面的优化要快,还是操作系统层面做乘法快,但此处之所以提出快速乘法是为了解决数long * long的溢出问题,一旦溢出%n的答案就不再正确,所以与其在相乘后求mod,还不如在计算过程当中不断取mod,避免溢出问题。

long a ,long b, long n,求:(a * b) % mod

思路很简单,把乘法看成加法即可,但怎么讲究效率,且有规律的办法是每次把问题规模缩减一半,所以快速取模乘法的时间复杂度为O(logn)O(\log n)

唉,其实用到的是二进制换十进制的计算法则,但没想到这种法则,能够让乘法从O(n)O(n)提高到O(logn)O(\log n),神奇。

eg:
a = a, b = 13
13  12  6  3  2  1
a   2a  4a 5a 8a 13a

可能不够直观,但上述确实算法的执行流程,起初还纠结怎么来的,其实可以把13用二进制表示:
1101
所以,当遇到第一位为1时,ans += a;与此同时左移一位,且a = a + a,在第二位时,a = 2a
0110
再进行左移,a = 4a
0011
此时,第一位为1,ans += 4a, ans = 5a;接着左移,且a = 8a
0001
第一位为1,ans += 8a, ans = 13a,循环结束。

一句话可以总结,实际就是:
1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 13

刚开始真没意识到就是这样一个二进制转十进制的计算过程,呵呵,初中学过,写代码却不知道。从代码结构来看,复杂度很好分析,因为每次除2,类似于递归,深度为O(logn)O(\log n),代码如下:

public static long quickMul(long a, long b, long mod){
        long ans = 0;
        while (b != 0){
            if ((b & 1) != 0){
                b--;
                ans = (ans + a) % mod;
            }
            b >>= 1;
            a = (a + a) % mod;
        }
        return ans;
    }

还需要证明一件事:a * a mod n = (a mod n) * (a mod n) mod n或者更一般地,a * b mod n = (a mod n) * (b mod n) mod n,很容易,知道这样一个事实即可:

⌊xn−k⌋=⌊xn⌋−k

\lfloor \frac{x}{n} - k \rfloor = \lfloor \frac{x}{n} \rfloor - k k是整数,所以一个数在楼层之间浮动,并不影响它与地板的相对位置,很显然的一个结论,利用它就可以证明上述取模的正确性了。

继续快速幂,把乘法看成加法,自然地可以把指数看成乘法,用到的思路依旧是二进制计算表达式,这样就容易理解了。

代码如下:

public static long quickPow(long a, long b, long mod){
        long ans = 1;
        while (b != 0){
            if ((b & 1) != 0){
                b--;
                ans = quickMul(ans, a, mod);
            }
            b >>= 1;
            a = quickMul(a, a, mod);
        }
        return ans;
    }

特别提一句b–,可以省略,因为整数取下底奇数–的答案和直接奇数一个效果。

POJ 1930: Dead Fraction

这道题很是无语。。。0.22222…. 可以看成:

2/9
22/99
...
22222/99999

但这些情况,都是最基础的2/9

0.12368...
有多种情况:
0.12 + 0.00368368...
0.123 + 0.0006868...

所以可以有:
12/100 + 368/99900

答案呼之欲出,题目还要求虽小的分母,所以遍历各种情况,取分母最小即可。

代码如下:

    static class Fraction{
        long fz;
        long fm;

        public Fraction(long fz, long fm){
            long d = gcd(fz, fm);
            fz /= d;
            fm /= d;
            this.fz = fz;
            this.fm = fm;
        }

        public Fraction add(Fraction that){
            long a1 = this.fz;
            long b1 = this.fm;
            long a2 = that.fz;
            long b2 = that.fm;
            return new Fraction(a1 * b2 + b1 * a2, b1 * b2);
        }

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

        @Override
        public String toString() {
            return fz + "/" + fm;
        }
    }


    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        while (true){
            String str = in.next();
            if (str.equals("0")) break;
            str = str.substring(2, str.length() - 3);
            char[] digit = str.toCharArray();
            if (digit.length == 1 && digit[0] == '0'){
                System.out.println("0/1");
                continue;
            }
            Fraction min = new Fraction(1, Long.MAX_VALUE);
            for (int i = 0; i < digit.length - 1; ++i){
                long a1 = 0;
                long b1 = 1;
                for (int j = 0; j <= i; ++j){
                    a1 = a1 * 10 + digit[j] - '0';
                    b1 = b1 * 10;
                }
                Fraction f1 = new Fraction(a1, b1); 
                long a2 = 0;
                long b2 = 0;
                for (int j = i + 1; j < digit.length; ++j){
                    a2 = a2 * 10 + digit[j] - '0';
                    b2 = b2 * 10 + 9;
                }
                Fraction f2 = new Fraction(a2, b2 * b1);
                Fraction f3 = f1.add(f2);
                if (f3.fm < min.fm){
                    min.fz = f3.fz;
                    min.fm = f3.fm;
                }
            }

            long a1 = 0;
            long b1 = 0;
            for (int i = 0; i < digit.length; ++i){
                a1 = a1 * 10 + digit[i] - '0';
                b1 = b1 * 10 + 9;
            }
            Fraction f3 = new Fraction(a1, b1);
            if (f3.fm < min.fm){
                min.fz = f3.fz;
                min.fm = f3.fm;
            }
            System.out.println(min.toString());
        }
    }

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券