? ?今天分享下各種快速冪(有點(diǎn)坑),首先說(shuō)一下快速冪的原理，

以下以求a的b次方來(lái)介紹?[1]?

?

把b轉(zhuǎn)換成二進(jìn)制數(shù)。

?

該二進(jìn)制數(shù)第i位的權(quán)為 ?

?

例如

?

?

11的二進(jìn)制是1011

?

11 = 23×1 + 22×0 + 21×1 + 2o×1

?

因此，我們將a11轉(zhuǎn)化為算 ?

?

第一種方法(普通的快速冪)
#include<iostream> //適用范圍a,b,p 1e9 #include<cmath> #include<algorithm> #include<stack> #include<map> using namespace std; typedef long long ll;ll fastpower(ll a,ll b,ll p) //寫(xiě)一個(gè)快速冪的函數(shù) {ll ans = 1; while(b) //b的二進(jìn)制還有位數(shù){if(b & 1) //b為奇數(shù) 循環(huán){ans = ans * a % p;}a = a * a % p; // 2^n 增長(zhǎng)b >>= 1; // b右移一位}return ans % p; //防止b為0，而沒(méi)有模 p }int main() {ll a,b,p;cin>>a>>b>>p;cout<<fastpower(a,b,p)<<endl;return 0; }
第二種方法(第一種的強(qiáng)化版)
#include <stdio.h> //無(wú)敵的_int 128 可以無(wú)視a,b,p的范圍，這范圍真的惡心 a,b,p 1e18 typedef __int128 ll; longlong a_b_Mod_c(ll a, ll b, ll p)
{ll s = 1;while (b)
{if (b & 1)s = (s * a) % p;a = (a * a) % p;b >>= 1;}return (longlong) s % p; } int main()
{int t;longlong a, b, p;scanf("%d", &t);while (t--)
{scanf("%lld%lld%lld", &a, &b, &p);printf("%lld\n", a_b_Mod_c(a, b, p));}return0; }
第三種方法(普通快速冪的優(yōu)化，即也用了快速乘)
#include <iostream> using namespace std;typedef long long ll;ll q_mul(ll a, ll b, ll mod) //快乘
{ll ans=0;while(b)
{if(b & 1) ans=(ans+a)%mod;a=(a<<1)%mod;b>>=1;}return ans; }ll q_pow(ll a, ll b, ll mod) //快冪
{ll ans=1;while(b)
{if(b & 1) ans=q_mul(ans,a,mod);a=q_mul(a,a,mod);b>>=1;}return ans; }int main()
{ll a,b,mod;int n;cin>>n;while(n--){cin>>a>>b>>mod;cout<<q_pow(a,b,mod)<<endl; }}
Java代碼
import java.math.BigInteger; import java.util.Scanner;public class Main{public static void main(String[] args)
{Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 0; i < n; i++)
{BigInteger A = sc.nextBigInteger();BigInteger B = sc.nextBigInteger();BigInteger P = sc.nextBigInteger();System.out.println(A.modPow(B, P));}}}
最后的大招-python(變態(tài)，一般做大數(shù)的都用它，別問(wèn)我為什么，
一時(shí)用python一時(shí)爽，一直用python一直爽，貌似是py的整數(shù)類(lèi)的封裝問(wèn)題)
python

1,def fastExpMod(b, e, m):result = 1while e != 0:if (e&1) == 1:# ei = 1, then mulresult = (result * b) % me >>= 1# b, b^2, b^4, b^8, ... , b^(2^n)b = (b*b) % mreturn result t=int(input()) while t:t-=1a, b, c = map(int, input().split())print(fastExpMod(a,b,c))

2,n = int(input())for i in range(n):a, b, p = map(int, input().split())print(pow(a, b, p))

如果有錯(cuò)誤的地方懇請(qǐng)大家指出來(lái)。

?

$1\le T\le {10}^3$，$1\le A,B,P\le {10}^{18}$

轉(zhuǎn)載于:https://www.cnblogs.com/gauss191/p/10503732.html

總結(jié)

以上是生活随笔為你收集整理的各种快速幂(qaq)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。