【每日一题】快速幂【分治】2026/3/28

什么是分治
一个问题能一分为二或者一分为n个子问题，然后子问题又能被一分为二或者一分为n个子问题，直到子问题很小能知道答案，然后就可以求出所有子问题的答案，合并就是总问题的答案。

分治经典问题--快速幂

b的p次方等于 b的（p/2）次方*b的（p/2）次方

我们要知道余数的性质

import java.util.*;

public class Main {
    static long ans=0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long b=sc.nextInt();
        long p=sc.nextInt();
        long k=sc.nextInt();
        System.out.println(dfs(b,p,k));
    }
    public static long dfs(long b,long p,long k){
        if(p==1)return b%k;
        else{
            if(p%2==0){
                long x=dfs(b,p/2,k)%k;
                ans=(x*x)%k;
            }else{
                long x=dfs(b,p/2,k)%k;
                long y=dfs(b,p/2+1,k)%k;
                ans=(x*y)%k;
            }


        }
        return ans;
    }
}