当前位置: 代码迷 >> 综合 >> 快速幂与快速乘 二进制算法
  详细解决方案

快速幂与快速乘 二进制算法

热度:71   发布时间:2024-01-15 07:09:04.0

一.快速幂

描述

求 a 的 b 次方对 p 取模的值,其中 1≤a,b,p≤10^9

输入格式

三个用空格隔开的整数a,b和p。

输出格式

一个整数,表示a^b mod p的值。

样例输入

2 3 9

样例输出

8

二.快速乘

描述

求 a 乘 b 对 p 取模的值,其中 1≤a,b,p≤10^18。

输入格式

第一行a,第二行b,第三行p。

输出格式

一个整数,表示a*b mod p的值。

样例输入

2
3
9

样例输出

6

 

#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
///b&1取出b二进制位下表示的最低位
///b>>1舍弃最低位
ll quick_mul(ll a,ll b,ll p)///计算a*b %p
{ll ans=0;for(;b;b>>=1){if(b&1) ans=(ans+a)%p ;a=a*2%p;}return ans;
}
ll quick_qow(ll a,ll b,ll p)///计算a^b %p
{ll ans=1%p;///ans不能为1,b为0,p为1的情况不成立for(;b;b>>=1){if(b&1) ans=(ans*a)%p ;a=a*a%p ;}return ans;
}
int main()
{ll a,b,k,ans;cin>>a>>b>>k;cout<<quick_qow(a,b,k);return 0;
}

 

  相关解决方案