原理

将原数字改为二进制，使得$O(n)$的算法优化到$O(logn)$

代码

#include<cstdio>
typedef  long long num;
num ksm(num a,num p){
	//a^p
	num ans=1,b=a;
	while(p>0){
		if((p&1)==1)ans=ans*b;
		b*=b;
		p>>=1;
	}
	return ans;
}
num ksm(num a,num p,num q){
	//a^p modq
	num ans=1,b=a;
	while(p>0){
		if(p&1)ans*=b%q;
		b*=b%q;
		p>>=1;
	}
	return ans;
}