2016年做网站好不好,网站建设 收费,贵州省网站集约化建设,青岛百度代理公司【题解提供者】吴立强
解法一
思路
【快速幂】算法改版题。
面对 a b m o d p a\times b\mod p abmodp 这个结构#xff0c;直接求必然溢出 long long#xff0c;任何基本结构都不好使。
模仿快速幂算法是先将 b b b 二进制分解#xff08;假设 b b b 的二进制表示…【题解提供者】吴立强
解法一
思路
【快速幂】算法改版题。
面对 a × b m o d p a\times b\mod p a×bmodp 这个结构直接求必然溢出 long long任何基本结构都不好使。
模仿快速幂算法是先将 b b b 二进制分解假设 b b b 的二进制表示为 b 59 b 58 b 57 . . . b 2 b 1 b 0 b_{59}b_{58}b_{57}...b_2b_1b_0 b59b58b57...b2b1b0那么就有 a × b ∑ i 0 59 ( b i × a × 2 i ) a\times b \sum _{i0}^{59}(b_i\times a\times {2^i}) a×b∑i059(bi×a×2i)
由于加法取模可以对加法各部分先取模所以有 a × b m o d p ( ∑ i 0 59 ( ( b i × a × 2 i ) m o d p ) ) m o d p a\times b\mod p (\sum _{i0}^{59}((b_i\times a\times {2^i})\mod p))\mod p a×bmodp(∑i059((bi×a×2i)modp))modp
通过上面的式子我们将原本的 a × b a\times b a×b 经由 b b b 的二进制拆分转化成了 60 个因为 2 60 1 0 18 2^{60} 10^{18} 2601018子结构的乘积如果可以较为快速的处理出这 60 个子结构的值那么原式的值也就求出来了。 b b b 的二进制拆分并不难而 a a a 则需依次求解出 a × 1 , a × 2 , a × 4 , a × 8... a\times 1,a\times 2,a\times 4,a\times 8... a×1,a×2,a×4,a×8...注意到其每一项都是前一项的两倍通过递推也就可以做到依次求解了。
代码
#include iostream
using namespace std;
typedef long long ll;int main() {ll a, b, p;cin a b p;ll ans 0;while(b) {if(b 1) ans (ans a) % p;a (a a) % p;b 1;}cout ans;return 0;
}算法分析
本算法的时间复杂度为 O ( log ( b ) ) O(\log(b)) O(log(b))。
