挑战程序竞赛系列（15）：2.6快速幂运算

用户1147447

发布于 2019-05-26 09:54:21

4030

发布于 2019-05-26 09:54:21

文章被收录于专栏：机器学习入门

挑战程序竞赛系列（15）：2.6快速幂运算

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

练习题如下：

POJ 3641: Pseudoprime numbers

判断在当前基数a时，满足费马小定理的伪素数。

代码如下：

public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        while (true) {
            int p = in.nextInt();
            int a = in.nextInt();
            if (p == 0 && a == 0)
                break;
            if (a != quickPow(a, p, p)){
                System.out.println("no");
                continue;
            }
            if (isPrime(p)) System.out.println("no");
            else System.out.println("yes");
        }
    }

    public static boolean isPrime(int num){
        for (int i = 2; i * i <= num; ++i){
            if (num % i == 0) return false;
        }
        return true;
    }

    public static long quickMul(long a, long b, long mod) {
        long ans = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                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) {
                ans = quickMul(ans, a, mod);
            }
            b >>= 1;
            a = quickMul(a, a, mod);
        }
        return ans;
    }

POJ 1995: Raising Modulo Numbers

取模运算，水题。

代码如下：

public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int Z = in.nextInt();
        while ((Z--) != 0){
            int M = in.nextInt();
            int N = in.nextInt();
            long ans = 0;
            for (int i = 0; i < N; ++i){
                long a = in.nextLong();
                long b = in.nextLong();
                ans = (ans + quickPow(a, b, M)) % M;
            }
            System.out.println(ans);
        }
    }

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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年06月21日，如有侵权请联系 cloudcommunity@tencent.com 删除

github