快速幂

求 a 的 n 次方，一次次乘要 n 步。快速幂利用 a^n=(a^(n/2))^2，把指数不断折半，只需 O(log n) 步：long long qpow(long long a,long long n,long long p){ long long r=1; while(n){ if(n&1) r=r*a%p; a=a*a%p; n>>=1; } return r; }。