我要招人

去企业版

首页 > 试题广场 >

快速幂

[编程题]快速幂

热度指数：9770 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请你计算 $a^b\ mod\ p$ 的值。
一共有 $q$ 次询问。

输入描述:

第一行输入一个正整数  ，代表询问次数。
接下来每行输入三个正整数 ，代表一次询问。
数据范围：

输出描述:

对于每次询问，输出一个整数，代表  的值。

示例1

输入

2
2 2 6
3 4 10

输出

4
1

算法知识视频讲解

Java

躺平了的小太阳很俊朗

import java.io.*;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.*;

public class Main {

public static void main(String[] args) throws IOException {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

for (int i = 0; i < n; i++) {

int a = scan.nextInt();

int b = scan.nextInt();

int q = scan.nextInt();

System.out.println(quick(a, b, q));

}

private static int quick(int a, int b, int q) {

long res = 1;

long base = a;

while (b != 0) {

if (b % 2 == 1) {

res = res * base % q;

}

base = base * base % q;

b >>= 1;

}

return (int) res;

}

发表于 2025-03-23 15:49:19 回复(0)

Java

亚兰德尔

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        while (in.hasNextInt()) {
                        // 注意，用例中的数较大，用int会溢出
            long a = in.nextInt();
            long b = in.nextInt();
            long p = in.nextInt();
            System.out.println(quickPow(a,b,p));
        }
    }

    // 非递归
    public static long quickPow(long num, long pow, long p) {
        long result = 1l;
        while (pow > 0) {
            if((pow&1)>0){
                result = (result*num) % p;
            }
            pow >>= 1;
            num = (num*num) % p;
        }
        return result % p;
    }
}

发表于 2024-04-26 11:53:51 回复(0)