快速幂&快速乘
LL mult_mod(LL a, LL b, LL c) { a %= c; b %= c; LL ret = 0; LL tmp = a; while (b){ if (b & 1){ ret += tmp; if (ret > c) ret -= c;//直接取模慢很多 } tmp <<= 1; if (tmp > c) tmp -= c; b >>= 1; } return ret; } LL pow_mod(LL a, LL n, LL mod) { LL ret = 1; LL temp = a%mod; while (n){ if (n & 1) ret = mult_mod(ret, temp, mod); temp = mult_mod(temp, temp, mod); n >> 1; } return ret; }