89. a^b

求 a 的 b 次方对 p 取模的值。

输入格式

三个整数 a,b,p在同一行用空格隔开。

输出格式

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

数据范围

0≤a,b,p≤10^9
数据保证 p≠0

输入样例：

3 2 7

输出样例：

2

思路
快速幂板子
代码

import java.util.*;

public class Main {
    public static long pow(long a,long b,long p)
    {
        long res=1;
        while(b>0){
            if((b&1)==1) res=res*a%p;
            b>>=1;
            a=a*a%p;
        }
        return res%p;
    }
    public static void main(String[] args) {
        int a,b,p;
        Scanner sc=new Scanner(System.in);
        a=sc.nextInt();
        b=sc.nextInt();
        p=sc.nextInt();
        long ans=pow(a,b,p);
        System.out.println(ans);
    }
}