类似链家网站建设方案,梅州正在建设高铁线路,网站后端建设,运营管理的主要内容有哪些快速幂
理论 a n a a ⋯ a a^n a a \cdots a anaa⋯a#xff0c;暴力的计算需要 O(n) 的时间。 快速幂使用二进制拆分和倍增思想#xff0c;仅需要 O(logn) 的时间。
对 n 做二进制拆分#xff0c;例如#xff0c; 3 13 3 ( 1101 ) 2 3 8 ⋅ 3 4 ⋅ 3 1 3^{13}…快速幂
理论 a n a × a × ⋯ × a a^n a × a × \cdots × a ana×a×⋯×a暴力的计算需要 O(n) 的时间。 快速幂使用二进制拆分和倍增思想仅需要 O(logn) 的时间。
对 n 做二进制拆分例如 3 13 3 ( 1101 ) 2 3 8 ⋅ 3 4 ⋅ 3 1 3^{13} 3^{(1101)_2} 3^8 \cdot 3^4 \cdot 3^1 3133(1101)238⋅34⋅31 对 a 做平方倍增例如 3 1 , 3 2 , 3 4 , 3 8 ⋯ ⋯ 3^1, 3^2, 3^4, 3^8 \cdots\cdots 31,32,34,38⋯⋯。
n 有 logn 1个二进制位知道了 a 1 , a 2 , a 4 , a 8 , ⋯ , a 2 logn a^1, a^2, a^4, a^8, \cdots, a^{2^{\text{logn}}} a1,a2,a4,a8,⋯,a2logn后只需要计算 logn 1 次乘法就可以了。 快速幂可以应用在任何具有结合律的运算中例如取模运算、矩阵乘法等。 例如 ( 3 13 ) % p ( ( 3 8 ) % p ⋅ ( 3 4 ) % p ⋅ ( 3 1 ) % p ) % p (3^{13})\%p ((3^8)\%p \cdot (3^4)\%p \cdot (3^1)\%p)\%p (313)%p((38)%p⋅(34)%p⋅(31)%p)%p 模板
int quickpow(int a, int n) {int res 1;while (n) {if (n 1) {res res * a;}a a * a;n 1;}return res;
}例题
P1226 【模板】快速幂 题目描述 给你三个整数 a , b , p a,b,p a,b,p求 a b m o d p a^b \bmod p abmodp。
输入格式 输入只有一行三个整数分别代表 a , b , p a,b,p a,b,p。
输出格式 输出一行一个字符串 a^b mod ps其中 a , b , p a,b,p a,b,p 分别为题目给定的值 s s s 为运算结果。
输入输出样例 #1
输入 #1
2 10 9输出 #1
2^10 mod 97说明/提示 样例解释 2 10 1024 2^{10} 1024 2101024 1024 m o d 9 7 1024 \bmod 9 7 1024mod97。
数据规模与约定 对于 100 % 100\% 100% 的数据保证 0 ≤ a , b 2 31 0\le a,b 2^{31} 0≤a,b231 a b 0 ab0 ab0 2 ≤ p 2 31 2 \leq p \lt 2^{31} 2≤p231。
#includebits/stdc.h
using namespace std;
int quickpow(long long a, long long b, long long p) {int res 1;while (b) {if (b 1) {res res * a % p;}a a * a % p;b 1;}return res;
}
int main() {long long a, b, p;cin a b p;cout a ^ b mod p quickpow(a, b, p);return 0;
}
理论
同余式 如果两整数a, b模m的余数相同则称a, b模m同余记为a ≡ b (mod m) 。例8 ≡ 2 (mod 3)
乘法逆元 若a, b互质且满足同余方程ax ≡ 1 (mod b)则称x为a模b的乘法逆元记作a⁻¹ 例8x ≡ 1 (mod 5)解得x 2, 7, 12…
费马小定理 若p为质数且a, p互质则a^(p - 1) ≡ 1 (mod p) 例4^(3 - 1) ≡ 1 (mod 3)
证明 构造一个与p互质的序列A {1, 2, 3, …, p - 1}现在来证明∏(i 1)^(p - 1) a × Ai ≡ ∏(i 1)^(p - 1) Ai (mod p) 每个a × Ai (mod p)的余数必是独一无二的且a × Ai (mod p) p 则必与Ai (mod p)的余数集合相同。故得证。 所以a^(p - 1) × ∏(i 1)^(p - 1) Ai ≡ ∏(i 1)^(p - 1) Ai (mod p) 。证毕。 例p 5, A {1, 2, 3, 4}, a 2。 则aA {2, 4, 6, 8}, aA%p {2, 4, 1, 3}, A%p {1, 2, 3, 4}
例题
给两个数a, pp是质数求a模p的乘法逆元
由费马小定理 a^(p - 1) ≡ 1 (mod p)得 a × a^(p - 2) ≡ 1 (mod p) 所以a^(p - 2) 就是a模p的乘法逆元。 用快速幂求即可。
#includebits/stdc.h
using namespace std;
int a, p;
int quickpow(int a, int b, int p) {int res 1;while (b) {if (b 1) {res res * a % p;}a a * a % p;b 1;}return res;
}
int main() {cin a p;if (a % p) {printf(%d\n, quickpow(a, p - 2, p));}return 0;
}
