题目描述

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

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

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

数据范围
0≤a,b,p≤109

输入样例：

3 2 7

输出样例：

2

算法

快速幂

例：计算 3*7

7的二进制 111
3*(2^0)=3
3*(2^1)=6
3*(2^2)=12

时间复杂度分析：logn

java

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        long a=sc.nextLong();
        long b=sc.nextLong();
        long p=sc.nextLong();
        long res=1%p;
        while(b!=0){
            int s=(int)((b&1)%p);
            if(s==1)    //只有b的二进制形式中的个位为1的时候，执行相乘（a*a）
               res=(res*a)%p;   
            b>>=1;  //右移，除二
            a=a*a%p;    
        }
        System.out.println(res);
    }
}

题目二

题目描述
求 a 乘 b 对 p 取模的值。
数据范围
1≤a,b,p≤10^18

样例
输入样例：

3
4
5

输出样例：

2

java

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        long a=sc.nextLong();
        long b=sc.nextLong();
        long p=sc.nextLong();
        long res=0;
        while(b!=0)
        {  
            int s=(int)((b&1)%p);
            if(s==1)
               res=(res+a)%p;
            b>>=1;
            a=2*a%p;
        }
        System.out.println(res);
    }
}