快速乘法计算模幂

2019-04-13 17:14发布

站内文章 / 模拟电子
17206 0 912
一般的快速模幂可能会产生整数溢出的情况 ，可以用快速乘法解决此问题 。 模板如下： #include #include #include #include #include using namespace std; long long mult_mod(long long a, long long b, long long c) { a %= c; b %= c; long long ret = 0; long long 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; } long long pow_mod(long long a, long long n, long long mod) { long long ret = 1; long long temp = a%mod; while (n) { if (n & 1)ret = mult_mod(ret, temp, mod); temp = mult_mod(temp, temp, mod); n >>= 1; } return ret; } int main() { long long a, n, mod; while (scanf("%lld%lld%lld", &a, &n, &mod) != EOF) { printf("%lld ",pow_mod(a,n,mod));//a^n%mod } }




热门文章