挑战程序竞赛系列(15):2.6快速幂运算

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

挑战程序竞赛系列(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;
    }

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券