<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">快速幂和快速等比数列和</span>
其中没用使用乘法逆元。。但是乘法逆元的更加快速,如果moddd数不是一个素数并且不好求他的欧拉函数,就可以使用等比数列的二分性。。。
但是速度比较慢、、
const int moddd = 1e9+7 ;
ll quick_pow(ll x , ll y){
if(y == 0) return 1 ;
ll tmp = quick_pow(x , y/2) ;
if(y & 1) tmp = (tmp * tmp % moddd) * x % moddd;
else tmp = tmp * tmp % moddd ;
return tmp %= moddd ;
}
ll quick_mi(ll m , ll a , ll b){
if(a == b) return quick_pow(m , a) ;
ll lz = (b - a + 1) ;
ll k = lz / 2 + a - 1;
ll tmp = quick_mi(m , a , k) ;
tmp = tmp * (1 + quick_pow(m , lz / 2)) % moddd ;
if(lz & 1) tmp = tmp + quick_pow(m , b) ;
return tmp % moddd ;
}
转载请注明原文地址: https://ju.6miu.com/read-1290962.html