快速模幂法

2019-04-13 13:23发布

用于求解 a b 次方,而b是一个非常大的数,用On)的复杂度会超时,这时就需要使用Ologn)的复杂度的快速模幂法进行求解   typedef long long ll; ll fun(ll x,ll n,ll mod) { ll res=1; while(n>0) { if(n&1)//相当于 if(n%2==1) res=(res*x)%mod; x=(x*x)%mod; n>>=1;//相当于n=n/2; } return res; } 练习: 51Nod_1046 A^B Mod C【水题】