当前位置 博文首页 > Light：快速幂运算， 快速幂取模运算，及慢速乘法
1.快速幂运算
求x的n次方， 或其对mod求模的问题用到快速幂运算， 代码如下非常简单， 这里做一点解释
typedef long long ll;
ll mod_pow(ll x, ll n)
{
ll ans = 1, base = x;
while(n > 0)
{
if(n & 1) ans = ans * base;//若n的二进制最低位是1, ans需要乘上base
base = base * base;
n >>= 1; //n二进制右移
}
return ans;
}
解释
例如x^22 = x ^ 16 * x ^ 4 * x ^ 2(22 的二进制是10110）
都可以做如上转换
带入上面代码， 首先n的二进制尾数为0， 不进行ans * base运算，
接下来base = x * x， n右移。
n二进制尾数是1 ans = ans * base， 一步步过去， ans陆续乘上x的二， 四， 十六次方， 函数返回最终结果。
2.对于快速幂后求模的添加一点即可
typedef long long ll;
ll mod_pow(ll x, ll n, ll mod)
{
ll ans = 1, base = x;
while(n > 0)
{
if(n & 1) ans = ans * base % mod;//若n的二进制最低位是1, res作为最终结果需要乘上x
base = base * base % mod;
n >>= 1; //n二进制右移
}
return ans;
}
3.慢速乘法
若数据过大可以看到ans * base会爆long long 的内存, 因为是先乘后求模，所以需要使得ans * base在mod的范围内， 这里就用到了慢速乘法。
ll mul(ll a, ll b, ll mod)
{
ll ans = 0, base = a;
while(b)
{
if(b & 1) ans = (ans + base) % mod;
base = (base + base) % mod;
b >>= 1;
}
return ans;
}
ll mod_pow(ll x, ll n, ll mod)
{
ll ans = 1, base = x % mod;
while(n)
{
if(n & 1) ans = mul(ans, base, mod); //慢乘， 其原理和快速幂相似。
base = mul(base, base, mod);
n >>= 1;
}
return ans;
}
牛客小白月赛12：B. 华华教月月做数学传送门
#include<iostream>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mul(ll a, ll b, ll mod)
{
ll ans = 0, base = a;
while(b)
{
if(b & 1) ans = (ans + base) % mod;
base = (base + base) % mod;
b >>= 1;
}
return ans;
}
ll mod_pow(ll x, ll n, ll mod)
{
ll ans = 1, base = x;
while(n)
{
if(n & 1) ans = mul(ans, base, mod);
base = mul(base, base, mod);
n >>= 1;
}
return ans;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
ll a, b, p;
scanf("%lld %lld %lld", &a, &b, &p);
printf("%lld\n", mod_pow(a, b, p));
}
}
