蓝桥杯基础数论学习笔记

目录：

  1. 素数（素数个数、最小素数，欧拉函数）
  2. 约数（约数个数公式）
  3. 幂 （快速幂）
  4. 阶乘 （阶乘的递推形式、阶乘与因数）
  5. 取模 （加减乘取模与除法取模、乘法逆元、中国剩余定理（待更新））
  6. 异或与异或和

一、素数

素数又称质数，一个大于1且只能被1和它本身整除的数被称为素数。对素数的求解往往是解决素数和约数问题的基础。

（1）求解方法

素数的求解有试除法、埃氏筛和线性筛三种求法，其中线性筛效率最高，此处只列出线性筛代码，因为线性筛不仅效率高，还可以方便地求出每个数的最小质因数，用途更广。
注意在考试的时候尽量打表，蓝桥杯的内存限制比较宽，一般不会出现内存溢出。不要让素数的搜索占用宝贵的程序运行时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 线性筛
def sieve(n):
    # find out all of the prime numbers between 2 and n
    prime = []
    is_prime = [True]*(n+1)
    for i in range(2,n+1):
        if is_prime[i]:
            prime.append(i)
        for j in prime:
            # 注意这三个操作的顺序不可调换
            if i*j > n:
                break
            is_prime[i*j] = False
            if i%j == 0:
                # 只用最小的质因数筛除非质数，减少了重复的运算
                # 因为j已经筛过一遍了，所以不需要用i重复筛了
                break           
    return prime

只需要对线性筛算法中筛除非质数的部分进行修改，在筛除某个值的同时记录筛除它的数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def sieve(n):
    prime = []
    is_prime = [True]*(n+1)
    min_prime = [1]*(n+1)
    for i in range(2,n+1):
        if is_prime[i]:
            prime.append(i)
            # 素数的最小质因子是它本身
            min_prime[i] = i
        for j in prime:
            if i*j > n:
                break
            is_prime[i*j] = False
            # 在排除数字i*j的同时记录它的最小质因子j
            # 注意此处i不一定是质数
            min_prime[i*j] = j
            if i%j == 0:
                break
    return min_prime

（2）求最小质因数

对于一个给定正整数，只需要从2开始逐个试除，第一个能够整除n的数就是其最小质因数。这个方法可以用反证法证明，如果第一个整除n的数是一个合数，那么n也一定可以被这个合数的每一个因数所整除，又因为合数存在小于其本身的因数，所以这个合数一定不是第一个能够整除n的数，这与假设矛盾，故原结论得证。

1
2
3
4
5
n = int(input())
for i in range(2,n+1):
    if n%i == 0:
        print(i)
        break

（3）欧拉函数

欧拉函数有一个输入n，返回所有小于等于n的数中与n互质的数的个数

性质一：欧拉函数的计算式

φ(a)=(1−1p1)∗(1−1p2)...(1−1pn)\varphi(a) = (1 - \frac 1 p_1)*(1 - \frac 1 p_2)...(1 - \frac 1 p_n)
其中 pip_i 是 nn 的所有质因子，如果 nn 中存在多个重复的质因子，这个质因子只计算一次

性质二：欧拉函数的分解

如果 (a%b==0且(a//b)%b==0)(a\%b == 0 且 (a//b)\%b == 0) 则有 φ(a)=φ(a//b)∗b\varphi(a) = \varphi(a//b)*b
如果 (a%b==0且(a//b)%b!=0)(a\%b == 0 且 (a//b)\%b != 0) 则有 φ(a)=φ(a//b)∗(b−1)\varphi(a) = \varphi(a//b)*(b-1)

推论一：

由性质二可知，φ(ab)=φ(a)∗ab−1\varphi(a^b) = \varphi(a) * a^{b-1}

1
2
3
4
5
6
7
8
9
10
11
# 利用性质一计算欧拉函数
def euler(n):
    res = n
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            while n%i == 0:
                n //= i
            res = res//i*(i-1)
    if n > 1:
        res = res // n * (n-1)
    return res

（4）例题演示

例题 1：分解质因数**

题目描述：

求出区间[a,b]中所有整数的质因数分解。

输入:

输入一行，包含两个用空格分割的正整数，分别表示 a 和 b。

输出:

每行输出一个数的分解，形如 k=a1∗a2∗a3...(a1<=a2<=a3...，k也是从小到大的)k=a_1* a_2 *a_3... (a_1<=a_2<=a_3...，k也是从小到大的)

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
33
# BF做法：直接对每一个在区间[a,b]内的数从2开始试除，但由于时间复杂度过高，一定会超时
# firstly,find out all the prime number that are smaller than n+1
def sieve(n):
    prime = []
    is_prime = [True]*(n+1)
    for i in range(2,n+1):
        if is_prime[i]:
            prime.append(i)
        for j in prime:
            if i*j > n:
                break
            is_prime[i*j] = False
            if i%j == 0:
                break
    return prime
# main part
a,b = map(int,input().split())
prime = sieve(b)
# divide every number in the interval
for i in range(a, b+1):
    print(f'{i} = ', end = '')
    # create a string to store the result of division
    line = [] 
    for j in prime:
        if i == 1:
            break
        while i%j == 0:
            line.append(str(j))
            line.append('*')
            i //= j
    # print the result of division
    line.pop(-1)
    print(''.join(line))

例题 2：互质数的个数

题目描述：

给定 a,b，求 1≤x＜ab1 ≤ x ＜ a^b中有多少个 xx 与 aba^b。由于答案可能很大，你只需要输出答案对 998244353 取模的结果。

输入:

输入一行，包含两个用空格分割的正整数，分别表示 a 和 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
# 带入欧拉公式推论一
# 快速幂 + 欧拉公式
MOD = 998244353
def qpow(a,n):
    ans = 1
    while n:
        if n&1:
            # n is odd
            ans = ans * a % MOD
        a = a * a % MOD
        n >>= 1
    return ans
def euler(n):
    res = n
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            while n%i == 0:
                n //= i
            res = res//i*(i-1)
    if n > 1:
        res = res//n*(n-1)
    return res

a,b = map(int,input().split())
if a == 1:
    print(0)
else:
    print(euler(a) * qpow(a,b-1) % MOD)

二、约数

约数又称因数，整数a除以非零整数b，除得的商正好是整数，余数为0，就说a能够被b整除，a是b的倍数，b是a的约数。

（1）求约数个数

约数个数定理：

对任意一个大于1的正整数 XX 都可以表示为若干个质数乘积的格式，即 X=P1a1∗P2a2∗...∗PkakX = P_1^{a_1} * P_2^{a_2} * ... * P_k^{a_k}，则约数的个数就是 (a1+1)∗(a2+1)∗...∗(ak+1)(a_1 + 1)*(a_2 + 1)*...*(a_k + 1)，注意这个结果中的约数包含1。

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
from collections import defaultdict
# calculate out the prime numbers that smaller than the given number
def sieve(n):
    prime = []
    is_prime = [True]*(n+1)
    for i in range(2, n+1):
        if is_prime[i]:
            prime.append(i)
        for j in prime:
            if i*j > n:
                break
            is_prime[i*j] = False
            if i%j == 0:
                break
    return prime
n = int(input())
prime = sieve(n)
# divide the given number by these prime numbers
# use a defaultdict to record the times that every number appear in the given number
d = defaultdict(int) 
for i in prime:
    while n%i == 0:
        d[i] += 1
        n //= i
# use the data to figure out the answer
ans = 1
for i in d.values():
    ans *= (i+1)
print(ans)

（2）求所有的约数

求约数的个数主要还是使用试除法，因为先计算所有质因数然后组合的时间复杂度过高，但也应注意到可以使用适当的优化提升算法的效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# BF algorithm
n = int(input())
res = []
for i in range(1, n+1):
    if i > (n//i):
        # all of the numbers that bigger than this value have alreadly been recorded
        break
    if n%i == 0:
        res.append(i)
        n //= i
        # record the number that left as well
        if n != i:
            res.append(n)
res.sort()
print(res)

（3）最大公因数

求两个数的最大公因数的方法有辗转相除法和更相减损术等，此处只介绍应用范围更广且时间复杂度更小的辗转相除法。辗转相除法，又名欧几里得算法，是一种可以利用递归或递推快速求除出两数最大公因数的算法，时间复杂度为 O(logn)O(logn)。

1
2
3
4
5
# 欧几里得算法
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

欧几里得算法既可以在考场时自己实现，也可以直接调用python的math标准库中的gcd()函数。

1
2
3
4
from math import gcd
m = 10
n = 6
print(gcd(m,n)) # output:2

（4）最小公倍数

求解定理：

最小公倍数 = 两数之积 // 最大公因数

1
2
3
from math import gcd
def gbs(a,b):
    return a*b//gcd(a,b)

三、幂

幂的运算可以使用python的运算符**实现，也可以自行建立快速幂函数。快速幂算法的时间复杂度是 O(logn)O(logn) ，虽然Python中有内嵌函数pow()，但调用的运行效率明显较低，最好自己写。

1
2
3
4
5
6
7
8
9
10
11
def qpow(a,n,mod):
    if n == 0:
        return 1
    res = 1
    while n:
        if n&1:
            # n is an odd number
            res = res * a % mod
        n >>= 1 # n need to be divided by 2
        a = a * a % mod
    return res

四、阶乘

阶乘是蓝桥杯的高频考点，基本上每年都有一道题，大部分是简单填空题，但大题还是比较难的，
主要需要注意其递推特性(n!=n∗(n−1)!n! = n*(n-1)!)和n与约数之间的关系。这里列出两道题目，分别涵盖以上两个难点。

例题 1：求阶乘（蓝桥杯第13届省赛真题）

题目描述：

满足 N!N! 的末尾恰好有 KK 个0的最小的 NN 是多少？输出这个数。如果这样的 NN 不存在，输出-1

输入格式：

输入一行，包含一个整数，表示k

输出格式：

输出一行，包含一个整数

提示：

对于 30%30\% 的数据，1≤K≤1061 \leq K \leq 10^6,
对于 100%100\% 的数据，1≤K≤10181 \leq K \leq 10^{18}

代码示例：

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
# 暴力做法，只能通过40%的样例
# 0只能通过乘以10的倍数或5的倍数获得，因为2的倍数远多于5的倍数，所以不用考虑
# 100，1200之类的数需要特别处理
from sys import exit

k = int(input())
if k < 0:
    print(-1)
    exit()
# 从5开始，以5为步长搜索5的倍数和10的倍数
n = 0 # 记录当前遍历到的因数
cur = 0 # 记录当前所得到的0的个数
while cur < k:
    n += 5
    # 先将n末尾所有的0转移到cur上
    temp = n
    while temp%10 == 0:
        temp //= 10
        cur += 1
    # 然后统计temp中5的个数
    while temp%5 == 0:
        temp //= 5
        cur += 1
if cur == k:
    print(n)
else:
    print(-1)

注意到对于一个给定的 n!n!，末尾0的个数 = 从1到n各个数字的约数中5的个数 = k
k=n51+n52+n53+...k = \frac n {5^1} + \frac n {5^2} + \frac n {5^3} + ... 可以高效地求出指定n!的末尾0个数，所以可以使用二分法提高查找效率。

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
# Binary Search Optimize
# 注意到末尾0的个数随n的增大只会增大，不会减小，且结果的末尾0个数有大于等于k和小于k两种状态，所以可以使用二分法高效求解
def check(n):
    # 求出 n! 末尾0的个数
    res = 0
    # 这个过程的实质是求出构成阶乘的数字中所有5的倍数，25的倍数，125的倍数...
    while n:
        n //= 5
        res += n
    return res

# binary search main part
k = int(input())
left = 1
right = 10**19
while left < right:
    mid = (left+right)//2
    if check(mid) < k:
        left = mid+1
    else:
        # mid 可能是正确答案，所以不能舍弃
        right = mid
# left = right
if check(left) == k:
    # 存在解
    print(left)
else:
    print(-1)

例题 2：阶乘的和（蓝桥杯第14届省赛真题）

题目描述：

给定 n 个数 AiA_i，问能满足 m! 为 ∑i=1n(Ai!)∑_{i=1}^n(A_i!) 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 1×2×3×⋅⋅⋅×m1 × 2 × 3 × · · · × m。

输入格式：

输入的第一行包含一个整数 n 。
第二行包含 n 个整数，分别表示 AiA_i，相邻整数之间使用一个空格分隔。

输出格式：

输出一行包含一个整数表示答案。

提示：

对于 40%40\% 的评测用例，n≤5000n ≤ 5000 ；
对于所有评测用例，1≤n≤105,1≤Ai≤1091 ≤ n ≤ 10^5,1 ≤ A_i ≤ 10^9

解题思路：
在极限情况下，a数组中各个值均只出现一次，各阶乘无法合并，那么m! = a[0]!,a[0] = min(a)
本题中各个a[i]可能重复出现，因此存在合并阶乘的可能(比如n!*(n+1) = (n+1)!)，所以m! = min(s)
s是合并化简后的a数组各元素阶乘和式子中阶乘元素的集合
通过以上分析可知m!应当是分子中各个阶乘合并后最小的阶乘
通过分治求出合并后的最小阶乘
temp = (x*a[0] + y*(a[0]+1)),x,y分别是a[0],a[0]+1在a中的个数
显然a[0]<=m，现在要看合并结果是否是a[0]+1的倍数，(a[0]+1)*y显然是(a[0]+1)的倍数

倍数性质：m的倍数+不是m倍数的数，则结果一定不是m的倍数

由倍数定律可知如果x*a[0]是(a[0]+1)的倍数，则temp就是(a[0]+1)的倍数
又因为gcd(a[0],a[0]+1) = 1，所以‘x*a[0]是(a[0]+1)的倍数’等价于x是(a[0]+1)的倍数

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
n = int(input())
a = sorted([int(i) for i in input().split()])
# 从最小的a[0]开始递推
# 创建一个变量记录当前阶乘的系数
k = 1
# 创建一个变量记录当前阶乘的值
cur = a[0]
for i in range(1,n):
    if cur == a[i]:
        k += 1
    else:
        # cur < a[i]
        # 检查系数是否能够合并进当前阶乘中
        while k%(cur+1) == 0 and k//(cur+1) != 0:
            cur += 1
            k //= cur
            if cur == a[i] :
                break
        # 无法达到a[i]
        if cur < a[i]:
            break
        else:
            # 成功到达a[i]
            k += 1
print(cur)

五、取模

竞赛题中常要求将较大的答案取模后输出，由于答案超出表示范围，所以不能先算出答案然后取模。此时，我们需要考虑如何在计算过程中进行取模才能获得所需答案。

（1）加减乘中的取模运算

加减法和乘法对取模运算是 封闭 的，也就是所在加减操作中添加取模运算时，既可以先分别对操作数进行取模然后运算，也可以先运算然后对结果取模，这两种方式所得结果是相同的。

(12 + 3)%10 = 5
12%10 = 2, 3%10 = 3
2 + 3 = 5

（2）除法中的取模运算

在除法运算中，先取模后运算将会得到错误答案，为了解决这一问题，学者引入了逆元。要求除法取模统一使用逆元解决。

（3）逆元

相关资料：逆元 —— 广义化的倒数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 逆元的求解 —— 拓展欧几里得
def exgcd(a, b):
    if b == 0:
        return a,1,0
    x1,y1,gcd = exgcd(b, a%b)
    x = y1
    y = x1 - (a//b)*y1
    return gcd,x,y

# 逆元求解主函数
def inv(a, p):
    gcd, x, y = exgcd(a, p)
    if gcd != 1:
        raise ValueError(f"The modular inverse does not exist for {a} mod {p}")
    # 返回 x%p 的结果
    return (x % p + p) % p

六、异或 & 异或和

异或操作是一种常用的二进制位运算，当两个操作数相同位上的数值不同时结果为1，数值相同的时候为0\

（1）基本性质

  1. 交换律：(a ^ b) = (b ^ a)
  2. 结合律：(a ^ b) ^ c = a ^ (b ^ c)
  3. 对于任何数x，都有x ^ x=0，x ^ 0 = x
  4. 自反性：a ^ b ^ b = a, a ^ 0 = a

例题 1：异或和（蓝桥杯第14届省赛）

问题描述：

给一棵含有 nn 个结点的有根树，根结点为 11 ，编号为 ii 的点有点权 aia_i （i∈[1,n]）（i \in [1,n]）。现在有两种操作，格式如下：
1xy1 x y ：该操作表示将点 xx 的点权改为 yy。
2x2 x ：该操作表示查询以结点 xx 为根的子树内的所有点的点权的异或和。
现有长度为 mm 的操作序列，请对于每个第二类操作给出正确的结果。

输入格式:

输入的第一行包含两个正整数 n,mn,m 用一个空格分隔。第二行包含 nn 个整数 $a_1, a_2, … ,a_n
，相邻整数之间使用一个空格分隔。接下来 n−1n−1 行，每行包含两个正整数 ui,viu_i, v_i，表示结点 uiu_i 和 viv_i之间有一条边。接下来 mm 行，每行包含一个操作。

输出格式:

输出若干行，每行对应一个查询操作的答案。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# 求 DFS 序，以便建立树状数组
cnt = 0
def dfs(cur,pre):
    # cur 是当前节点的序号，pre是上一个节点的序号
    global cnt
    cnt += 1
    # 记录将当前节点压入栈中的时间戳
    seq[cur][0] = cnt 
    for i in tree[cur]:
        if pre != i:
            dfs(i,cur)
    # 记录将当前元素出栈的时间戳，自此以后的时间戳均与以cur为根节点的树无关
    seq[cur][1] = cnt 

# 树状数组函数三件套
def lowbit(x):
    return x&(-x)

def modify(x,v):
    global n
    while x <= n:
        t[x] ^= v # 计算异或和
        x += lowbit(x)

def query(x):
    global n
    ans = 0
    while x > 0:
        ans ^= t[x]
        x -= lowbit(x)
    return ans

# 接收输入，创建数据结构
n,m = map(int,input().split())
# a[]存储每一个点的权值
a = [0] + [int(i) for i in input().split()]

# 用邻接表存储树结构
tree = [[] for i in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    # 注意没说方向，是一个无向边
    tree[u].append(v)
    tree[v].append(u)

# 创建一个二维数组seq[][]记录DFS序
# 其中seq[i]是有2个元素的列表，两个元素分别是第i个节点入栈和出栈的时间戳
seq = [[0,0] for i in range(n+1)]
dfs(1,0)

# 为DFS序数组创建树状数组，并用a[]的值初始化
t = [0]*(n+1)
for i in range(1,n+1):
    modify(seq[i][0], a[i])
for _ in range(m):
    instr = [int(i) for i in input().split()]
    if instr[0] == 1:
        # 修改元素，注意到需要在赋值的同时清除原有元素，所以将原值与新值异或，相当于清除原值
        modify(seq[instr[1]][0], a[instr[1]]^instr[2])
        # 维护a[]，确保其始终保存着每一个节点的当前值
        a[instr[1]] = instr[2]
    else:
        # 输出单点查询结果 
        print(query(seq[instr[1]][1]) ^ query(seq[instr[1]][0] - 1))