[[TOC]]
解释
现在我们需要求b a s e b base ^ b ba s e b b b b b b b 1 0 9 10^9 1 0 9
显然: ++任意一正整数都可以唯一的表示成若干个不重复的2的次幂的和++,也就是可以唯一的写成对应的二进制形态.
那么如果设b b b k k k i ( 0 ⩽ i < k ) i(0 \leqslant i < k) i ( 0 ⩽ i < k ) c i c_i c i c i ∈ 0 , 1 c_i \in {0,1} c i ∈ 0 , 1 b b b
b = c k − 1 2 k − 1 + c k − 2 2 k − 2 + ⋯ + c 0 2 0 (1)
b =c_{k-1} 2^{k-1} + c_{k-2} 2^{k-2} + \cdots + c_0 2^0
\tag 1
b = c k − 1 2 k − 1 + c k − 2 2 k − 2 + ⋯ + c 0 2 0 ( 1 ) 结合指数幂分配律: a m + n = a m × a n a^{m+n} = a^m \times a^n a m + n = a m × a n
a b = a c k − 1 2 k − 1 × a c k − 2 2 k − 2 + ⋯ + a c 0 2 0 (2)
a ^ b = a^{c_{k-1} 2^{k-1}} \times a^{c_{k-2} 2^{k-2}} + \cdots + a^{c_0 2^0} \tag 2
a b = a c k − 1 2 k − 1 × a c k − 2 2 k − 2 + ⋯ + a c 0 2 0 ( 2 ) 再根据幂乘方律: ( a m ) n = a m n (a^m)^n = a^{mn} ( a m ) n = a mn a 2 i = a 2 i − 1 ⋅ 2 = ( a 2 i − 1 ) 2 a^{2^i} = a^{2^{i-1} \cdot 2} = (a^{2^{i-1}})^2 a 2 i = a 2 i − 1 ⋅ 2 = ( a 2 i − 1 ) 2 a b a^b a b
又一个显然的数学常识,整数b b b ⌈ l o g 2 ( b + 1 ) ⌉ \lceil log_2^{(b+1)} \rceil ⌈ l o g 2 ( b + 1 ) ⌉ a b a^b a b ⌈ l o g 2 ( b + 1 ) ⌉ \lceil log_2^{(b+1)} \rceil ⌈ l o g 2 ( b + 1 ) ⌉
代码模板
综上,可以写下面的代码.
template < typename T = long long >
T quick_pow ( T base, T b , T mod) {
T ans = 1 % mod;
for ( ; b; b>>= 1 )
{
if ( b & 1 )
ans = ans * base % mod;
base = base * base % mod;
}
return ans;
}
复制
题目