MOD指数演算

mod_exp.cpp

const int MOD = 1000000007;

long long
mod_mult(long long a,long long b)
{
  long long res = 0;
  long long mir = a%MOD;
	while (b) {
		if (b&1) {
			res += mir;
			if (res > MOD) {
				res -= MOD;
			}
		}
		mir <<= 1;
		if (mir > MOD) {
			mir -= MOD;
		}
		b >>= 1;
	}
	return res;
}

long long
mod_exp(long long a,long long b)
{
	long long res = 1;
	long long mir = a%MOD;
	while (b) {
		if (b&1) {
			res = mod_mult(res, mir);
		}
		mir = mod_mult(mir, mir);
		b >>= 1;
	}
	return res;
}