洛谷例题

推荐自行脑补：百度百科

如果，那么；

前言：快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)，与朴素的O(N)相比效率有了极大的提高。

拿题目样例

Input ：2 10 9

Output：7

2¹⁰% 9 = 7 没毛病

问题不大那么真正的问题是怎么算这个

普通幂:废物过程可你有没有发现这个很烦？

可是算到2⁶⁴就炸了qwq （__int128啥的给我走开）

b=2,p=10,k=9

2^1=2 2%9=2

2^2=4 4%9=4

2^3=8 8%9=8

2^4=16 16%9=7

2^5=32 32%9=5

2^6=64 64%9=1

2^7=128 128%9=2
2^8=256 256%9=4
2^9=512 512%9=8
2^10=1024 1024%9=7

递推幂：甚至还可以在优化成 b^k-1%p*b

其实也就是递推这样就好一丢丢吧大数字的时候可以这样暂且优化一下（至少不容易爆精度）

也是比较有实用性的 orz 这样就可以得到

a[] = b ;

    for (register int i=;i<=k;i++) a[i] = a[i-] % p * b ;

这样不就是个递推了吗海星用数组只是好理解而且不太会爆精度不知道多少分（应该比较优秀的分数吧）

b=,p=,k=

%=

2*2%=

4*2%=

8*2%=

7*2%=

5*2%=

1*2%=2
2*2%9=4 
4*2%9=8 
8*2%9=7

看图其实有一部分是循环节（我还复制了）可以通过循环节来处理加速（不建议）万一没有循环节呢

mod：是时候叫出快速幂（超级飞侠）来帮忙了每次遇到困难...（不玩梗了）

快速幂：

快速幂代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

inline LL quickpow (LL x , LL y , LL mod){ LL ans = ;//自定义函数可作为快速幂模型

    for ( ; y ; x = x * x % mod , y >>= ) y &  ? ans = ans * x % mod : ;

    return (LL) ans % mod ;

}

signed main() {

    LL b,k,p;

    cin >> b >> k >> p ;

    cout << b << '^' << k << " mod " << p << '=' << quickpow(b , k , p) << endl ;

    return ;

}

这个代码可以作为模板使用

（背就完事了哪那么多话）

巴特西

quickpow || 快速幂

洛谷例题

快速幂代码

最新文章

热门文章