【每日一题】快速幂【差分】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;}
}