问题：
给定整数 a , b , p a,\ b,\ p a , b , p a b m o d p a^b\mod p a b mod p ( 1 ≤ a , b , p ≤ 10 9 ) (1 \le a,b,p \le 10^9) ( 1 ≤ a , b , p ≤ 1 0 9 )
分析：
我们可以将 b b b
b = c 0 2 0 + c 1 2 1 + c 2 2 2 + . . . + c k − 1 2 k − 1 b = c_02^0+c_12^1+c_22^2+...+c_{k-1}2^{k-1} b = c 0 2 0 + c 1 2 1 + c 2 2 2 + ... + c k − 1 2 k − 1 其中 c n c_n c n 0 0 0 1 1 1
那么有：
a b = a c 0 2 0 + c 1 2 1 + c 2 2 2 + . . . + c k − 1 2 k − 1 a^b = a^{c_02^0+c_12^1+c_22^2+...+c_{k-1}2^{k-1}} a b = a c 0 2 0 + c 1 2 1 + c 2 2 2 + ... + c k − 1 2 k − 1 a b = a c 0 2 0 a c 1 2 1 a c 2 2 2 . . . a c k − 1 2 k − 1 a^b = a^{c_02^0}a^{c_12^1}a^{c_22^2}...a^{c_{k-1}2^{k-1}} a b = a c 0 2 0 a c 1 2 1 a c 2 2 2 ... a c k − 1 2 k − 1 并且我们知道
a 2 n = ( a 2 n − 1 ) 2 a^{2^{n}} = (a^{2^{n-1}})^2 a 2 n = ( a 2 n − 1 ) 2 故我们只需要递推即可得出每个乘积项，当 c n = 1 c_n = 1 c n = 1
代码：
int quickPower ( int a , int b , int p ) { int ans = 1 % p; while (b) { if (b & 1 ) ans = ( long long )ans * a % p; b >>= 1 ; a = ( long long )a * a % p; } return ans; } 例题 :
89. a^b - AcWing题库
问题：
给定整数 a , b , p a,\ b,\ p a , b , p a × b m o d p a\times b\mod p a × b mod p ( 1 ≤ a , b , p ≤ 10 18 ) (1 \le a,b,p \le 10^{18}) ( 1 ≤ a , b , p ≤ 1 0 18 )
分析：
由于long long只能存 9 × 10 18 9\times 10^{18} 9 × 1 0 18 b b b
b = c 0 2 0 + c 1 2 1 + c 2 2 2 + . . . + c k − 1 2 k − 1 b = c_02^0+c_12^1+c_22^2+...+c_{k-1}2^{k-1} b = c 0 2 0 + c 1 2 1 + c 2 2 2 + ... + c k − 1 2 k − 1 然后有
a × b = c 0 a 2 0 + c 1 a 2 1 + c 2 a 2 2 + . . . + c k − 1 a 2 k − 1 a\times b = c_0a2^0+c_1a2^1+c_2a2^2+...+c_{k-1}a2^{k-1} a × b = c 0 a 2 0 + c 1 a 2 1 + c 2 a 2 2 + ... + c k − 1 a 2 k − 1 又因为
a 2 n = ( a 2 n − 1 ) × 2 a2^n = (a2^{n-1})\times 2 a 2 n = ( a 2 n − 1 ) × 2 如果我们得到 a 2 n − 1 m o d p a2^{n-1}\mod p a 2 n − 1 mod p ( a 2 n − 1 ) × 2 m o d p (a2^{n-1})\times 2 \mod p ( a 2 n − 1 ) × 2 mod p
同样当 c i = 1 c_i = 1 c i = 1
代码：
long long mul ( long long a , long long b , long long p ) { long long ans = 0 ; while (b) { if (b & 1 ) ans = (ans + a) % p; a = (a * 2 ) % p; b >>= 1 ; } return ans; } 例题：
90. 64位整数乘法 - AcWing题库
将一个长度为 m m m
利用位运算实现原 bool 数组中对应下标元素的存取。
操作 运算 取出 n n n k k k (n>>k) & 1 取出 n n n 0 0 0 k − 1 k-1 k − 1 k k k n & ((1<<k)-1) 将第 k k k n xor (1<<k) 将第 k k k 1 1 1 n | (1<<k) 将第 k k k 0 0 0 n & (~(1<<k))
位运算的一个重要特点：在二进制表示下不进位，参与位运算的各个二进制位之间是独立无关的
例题：
998. 起床困难综合症 - AcWing题库
对于非负整数 n n n
当 n n n n x o r 1 = n − 1 n\ xor\ 1 = n-1 n x or 1 = n − 1
当 n n n n x o r 1 = n + 1 n\ xor\ 1 = n+1 n x or 1 = n + 1
因此，0和1、2和3、4和5...都是关于xor 1运算成对变换
常用于邻接表中无向边 的存取
lowbit(n) 定义为非负整数 n n n 1 1 1 0 0 0
因为在计算机中 [ − x ] 补 = [ x ] 补 按位取反 + 1 [-x]_补 = [x]_补\ 按位取反 + 1 [ − x ] 补 = [ x ] 补 按位取反 + 1
所以有
l o w b i t ( n ) = n & ( ∼ n + 1 ) = n & ( − n ) lowbit(n) = n\ \&\ (\sim n+1) = n\ \&\ (-n) l o w bi t ( n ) = n & ( ∼ n + 1 ) = n & ( − n ) 通过 lowbit 运算，我们可以找到整数二进制表示下所有是 1 1 1
迭代计算 n = n − l o w b i t ( n ) n = n - lowbit(n) n = n − l o w bi t ( n ) n n n 0 0 0 1 1 1 0 0 0 l o g 2 x log_2x l o g 2 x
这里求对数可以预处理，建立一个长度为 37 37 37 H H H H [ 2 k m o d 37 ] = k H[2^k \mod 37] = k H [ 2 k mod 37 ] = k ∀ k ∈ [ 0 , 35 ] , 2 k m o d 37 \forall k \in [0,35], 2^k \mod 37 ∀ k ∈ [ 0 , 35 ] , 2 k mod 37
int H[ 37 ]; for ( int i = 0 ;i < 37 ;i ++ ) H[( 1 ll << i) % 37 ] = i; while (cin >> n) { while (n > 0 ) { cout << H[(n & - n) % 37 ]; n -= (n & - n); } } lowbit也是树状数组的一个基本运算