题目描述

求 a 的 b 次方对 p 取模的值，其中 0≤a,b,p≤10^9​

输入描述:

三个用空格隔开的整数a,b和p。

输出描述:

一个整数，表示 a^b mod p 的值。

输入

2 3 9

输出

8

分析

这题其实就是用快速幂写，不过就是要注意以下n == 0且p == 1时的情况，需要特判以下，因为任何非负数 mod 1都为0，如果不特判最后就会返回 1，与实际不符

AC代码

 1 import java.util.Scanner;
 2 
 3 public class Main {
 4     public static void main(String[] args) {
 5         Scanner input = new Scanner(System.in);
 6         int a = input.nextInt();
 7         int b = input.nextInt();
 8         int p = input.nextInt();
 9         long res = qpow(a, b, p);
10         System.out.println(res);
11     }
12     
13     public static long qpow(long a, long n, long mod) {
14         if (a == 0) {
15             return 0;
16         }
17         
18         // 任何一个非负数对1求模，都是0，因为1都是他们的公约数
19         // 这里需要他特判一下
20         if (n == 0) {
21             if (mod != 1) {
22                 return 1;
23             }
24             return 0;
25         }
26         
27          long ans = 1;
28          while (n != 0) {
29              if (n % 2 == 1) {
30                  ans *= a;
31                  ans %= mod;
32              }
33              a *= a;
34              a %= mod;
35              n = n >> 1;
36          }
37         
38         return ans;
39     }
40 }

牛客链接：https://ac.nowcoder.com/acm/contest/996/A