洛谷模板汇总算法基础 python解析

P1226 【模板】快速幂

题目分析

快速幂原理：
以这个为例 $a=2,b=(11)_{10}=(1011)_{2}$ ，求 $2^{11}。$
$2^{11}=2^{8} \times 2^{0} \times 2^{2} \times 2^{1}$ ，幂的次数正好对应 $1011)_{2}$
那么只需循环判断即可。

“”“
ans = 1
base = a = 2^1

第一次循环
b = 12 = '0b1011'  # 0b是python里的二进制标志
1 = '0b0001'
b & 1 = '0b0001' = 1
ans = ans * base = 1 * 2 = 2
base = 2^2
b = b >> 1 = '0b101'

第二次循环
b & 1 = '0b001' = 1
ans = 2 * 2^2 = 2^3
base = 2^4
b = b >> 1 = '0b10'

第三次循环
b & 1 = '0b00' = 0
base = 2^8
b = b >> 1 = '0b1'

第四次循环
b & 1 = '0b1' = 1
ans = 2^3 * 2^8 = 2^11
base = 2^16
b = b >> 1 = 0 # b=0 退出循环

最后的ans = 2^11.
计算次数由O(b) => log(b)
”“”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

通常对于快速幂一般结合取余(mod)来考。了解原理即可
$\, mod \, P = (A \, mod \, P + B \, mod \,P)\,mod\,P$
$\times B)\,mod\,P=((A\,mod\,P) \times (B\,mod\,P))\,mod\,P$
见代码。

代码

# 快速幂
def quickpower(a: int, b: int):
    base = a
    ans = 1
    while b > 0:
        if b & 1:
            ans *= base
        base *= base
        b = b >> 1
    return ans
  
# 快速幂应用--取余 
def quickmod(a: int, b: int):
    base = a
    ans = 1
    while b > 0:
        if b & 1:
            ans *= base
            ans %= p
        base *= base
        base %= p
        b = b >> 1
    return ans

a, b, p = map(int, input().split())
# 只能过一半百分之五十
# ans = quickpower(a, b) % p
# print(f"{a}^{b} mod {p}={ans}")
# AC
ans = quickmod(a, b)
print(f"{a}^{b} mod {p}={ans}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

P3367 【模板】并查集

题目地址：【模板】并查集

题目分析

这个找并集就是找他们共同的祖先。就以题目例题来看.

"""
n = 4, m = 7
fa = [0, 1, 2, 3, 4]

① 1、2的祖先分别为1、2 不相等，输出N
② 将1、2合并，设2为1的祖先，fa = [0, 2, 2, 3, 4]
③ 1、2的祖先分别为2、2 相等，输出Y
④ 将3、4合并，设4为3的祖先，fa = [0, 2, 2, 4, 4]
⑤ 1、4的祖先分别为2、4 不相等，输出N
⑥ 将2、3合并，设3是2的祖先，fa = [0, 2, 3, 4, 4]
⑦ 1的爸爸是2，2的爸爸是3，3的爸爸是4 => 1的祖先是4
  4的祖先是4
  相等输出Y
"""
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这个找祖先的函数递归一下就可以了。
见代码

代码

# 递归找爹
def find(x):
    if x == fa[x]:
        return x
    fa[x] = find(fa[x])
    return fa[x]

n, m = map(int, input().split())
fa = [i for i in range(n+1)]  # 初始化自己为爹
for _ in range(m):
    z, x, y = map(int, input().split())
    a, b = find(x), find(y)
    if z == 1:
        fa[a] = b
    else: # z == 2
        if a == b:
            print('Y')
        else:
            print('N')         
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19