数学与数论类题目练习

2025-03-16 · 7 分钟阅读 · 算法数据结构数学数论贪心策略 gcd 质数筛深搜扩展 gcd 栈快速幂线性代数 ·

复制链接:

文章目录

前几天光往医院跑，没大抽出时间做题。

题目来自 AcWing

重要

对于任意大于 $1$ 的整数 $N$ ，分解质因数得 $N=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}$ ， $N$ 的因数个数为 $(a_1+1)(a_2+1)\cdots(a_k+1)$ ， $N$ 的因数之和为 $(1+p_1+p_1^2+\cdots+p_1^{a_1})(1+p_2+p_2^2+\cdots+p_2^{a_2})\cdots(1+p_k+p_k^2+\cdots+p_k^{a_k})$ 。

1246. 等差数列 | 原题链接

给出的数据中，令其中的最小项为首项，最大项为末项，且公差最大时，项数最少。对给出的数据排序并两两作差，当公差为这些差的最大公约数时最大，此时项数最少。

 1n = int(input())
 2nums = list(map(int, input().strip().split()))
 3nums.sort()
 4
 5if nums[-1] == nums[0]:
 6    print(n)
 7    exit()
 8
 9def gcd(a, b):
10    return a if b == 0 else gcd(b, a % b)
11
12b = list()
13for i in range(1, n):
14    b.append(nums[i] - nums[i - 1])
15
16g = b[0]
17for i in range(n - 1):
18    g = gcd(g, b[i])
19print((nums[-1] - nums[0]) // g + 1)

python

1295. X的因子链 | 原题链接

因子链中的每一个数都是前面任意一个数的倍数，同时也是原数字的因数，这也就是说，因子链中后一个数是前一个数乘上一个因子得到的。为了确保因子链尽可能长，前一个数乘的因子要尽量小，即质因数，此时因子链的长度为原数字中质因数的个数。

求这样长度的因子链有多少个，是一个排列组合的问题，即求这些质因子能够组成多少种不同的序列。假设第 $i$ 种质因子出现了 $a_i$ 次，则有 $r=\frac{(\sum a_i)!}{\prod(a_i!)}$ 种不同的序列。

 1import sys
 2from collections import defaultdict
 3
 4
 5primes = [2]
 6visited = [False] * (2**20 + 1)
 7for i in range(3, 2**20 + 1, 2):
 8    if not visited[i]:
 9        primes.append(i)
10        for j in range(i * i, 2**20 + 1, i):
11            visited[j] = True
12
13
14def factorial(x):
15    if x == 0 or x == 1:
16        return 1
17    ans = 1
18    for i in range(2, x + 1):
19        ans *= i
20    return ans
21
22
23def mul(x):
24    ans = 1
25    for i in x:
26        ans *= i
27    return ans
28
29
30data = map(int, sys.stdin.read().strip().split())
31for x in data:
32    factors = defaultdict(int)
33    for p in primes:
34        if p * p > x:
35            break
36        while x % p == 0:
37            x //= p
38            factors[p] += 1
39    if x > 1:
40        factors[x] += 1
41    exp = tuple(factors.values())
42    print(factors)
43    a = sum(exp)
44    b = factorial(sum(exp)) // mul(factorial(e) for e in exp)
45    print(a, b)

...

python

1296. 聪明的燕姿 | 原题链接

由于已知对于一个大于 $1$ 的整数 $N$ ，分解质因数得 $N=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}$ ， $N$ 的因数之和为 $(1+p_1+p_1^2+\cdots+p_1^{a_1})(1+p_2+p_2^2+\cdots+p_2^{a_2})\cdots(1+p_k+p_k^2+\cdots+p_k^{a_k})$ 。因此我们可以使用深搜，依次枚举每一组 $(1+p_i+p_i^2+\cdots+p_i^{a_i})$ ，同时特判满足 $s=p_i+1$ 的值。

 1import sys
 2from functools import lru_cache
 3
 4data = tuple(map(int, sys.stdin.read().strip().split("\n")))
 5MAX = 2e9
 6SQRT_MAX = int(MAX**0.5 + 1)
 7primes = [2]
 8visited = [False] * SQRT_MAX
 9for i in range(4, SQRT_MAX, 2):
10    visited[i] = True
11
12for i in range(3, SQRT_MAX, 2):
13    if not visited[i]:
14        primes.append(i)
15        for j in range(i * i, SQRT_MAX, i):
16            visited[j] = True
17
18
19@lru_cache(maxsize=None)
20def is_prime(x):
21    for i in range(2, int(x**0.5) + 1):
22        if x % i == 0:
23            return False
24    return True
25
26
27@lru_cache(maxsize=None)
28def dfs(last, curr, rest):
29    if rest == 1:
30        ans.add(curr)
31        return
32
33    if is_prime(rest - 1) and rest - 1 > primes[(last if last > 0 else 0)]:
34        ans.add(curr * (rest - 1))
35
36    for i in range((last + 1), len(primes)):
37        if primes[i] > rest**0.5 + 1:
38            break
39        p = primes[i]
40        s = 1 + p
41        m = p
42        while s <= rest:
43            if rest % s == 0:
44                dfs(i, curr * m, rest // s)
45            m *= p
46            s += m
47
48
49for S in data:
50    ans = set()
51    dfs(-1, 1, S)
52    print(len(ans))
53    if len(ans) > 0:
54        print(*sorted(list(ans)))

...

python

可以过 13/14 个测试点，最后一个测试点一直 WA，调半天也不知道哪有问题……

1299. 五指山 | 原题链接

重要

裴蜀定理：若 $a,b$ 是整数,且 $GCD(a,b)=d$ ，那么对于任意的整数 $x,y$ 都有 $d|(ax+by)$ 。特别地，一定存在整数 $x,y$ 使得 $ax+by=d$ 成立。

解方程 $ax+by=GCD(a,b)$ 可以通过扩展欧几里得算法解决，模板如下：

1def exgcd(a, b):
2    if b == 0:
3        return 1, 0
4    else:
5        x, y = exgcd(b, a % b)
6        return y, x - a // b * y

python

该算法可用于解线性同余方程，如本题。

假设当大圣到达 $y$ 时一共翻了 $m$ 次筋斗云，那么可以列出同余方程 $md+x\equiv y\space(mod\space n)$ ，也可写作 $n|md+x-y$ 或者 $kn=md+x-y$ ；
若方程有解，根据裴蜀定理可知一定有 $GCD(d,n)|y-x$ ，否则方程无解。若方程有解，此时可以使用扩展欧几里得算法求出线性同余方程的一组解 $m_0,k_0$ ；
根据线性同余方程解的结构计算出 $m=m_0\cdot\frac{y-x}{GCD(d,n)}$ ；
因为大圣只能逆时针移动，即需要 $m>0$ ，因此令 $m=m\space mod\space(\frac{n}{GCD(d,n)})$ 。方程所有有效的解都是以循环方式出现的。有效解的集合可以表示为： $m=m_0+p\cdot\frac{n}{GCD(d,n)}$ ，所有解以 $\frac{n}{GCD(d,n)}$ 为步长。

 1def gcd(a, b):
 2    return a if b == 0 else gcd(b, a % b)
 3
 4
 5def exgcd(a, b):
 6    if b == 0:
 7        return 1, 0
 8    else:
 9        x, y = exgcd(b, a % b)
10        return y, x - a // b * y
11
12
13T = int(input().strip())
14for _ in range(T):
15    n, d, x, y = map(int, input().strip().split())
16    if (y - x) % gcd(d, n) != 0:
17        print("Impossible")
18        continue
19    m0, k0 = exgcd(d, n)
20    m = m0 * (y - x) // gcd(d, n)
21    m %= n // gcd(d, n)
22    print(m)

python

1223. 最大比例 | 原题链接

辗转相减法求最大公约数： $GCD(a,b)=GCD(b,a-b)\space(a\geq b)$

题目要求的是公比可能的最大值。假设一个符合条件的公比最简形式为 $\frac{m}{n}$ ，即其中 $m,n$ 互质且 $\frac{m}{n}$ 不能表示为另一个最简分数整数次幂的形式。令题目要求的值为 $q^k$ ，即 $\frac{m^k}{n^k}$ 。

根据题目的数据可以直接求出 $q^a,q^b,\cdots$ ，将分子与分母分别表示为 $\frac{m^a}{n^a},\frac{m^b}{n^b},\cdots$ 。因为对于 $\forall i,\frac{m^i}{n^i}=(\frac{m^k}{n^k})^{\alpha_1}$ ，所以 $k=GCD(a,b,\cdots)$ 。

又因为 $q^{GCD(a,b,\cdots)}=GCD(q^a,q^b,\cdots)$ ，不妨分别求 $GCD(m^a,m^b,\cdots)$ 和 $GCD(n^a,n^b,\cdots)$ 再输出。不过这里的 $GCD$ 需要用辗转相减法求而非传统的辗转相除法。如果要用辗转相除法做，需要将每个数分解质因数，然后再对每个质因子的次数求最大公约数。

假设 $f(q^x,q^y)=q^{GCD(x,y)}$ ，因此有 $\begin{aligned} & f(q^x,q^y) \\ =&q^{GCD(x,y)} \\ =&q^{GCD(x,y-x)} \\ =&f(q^x,q^{y-x}) \\ =&f(q^x,\frac{q^y}{q^x}) \end{aligned}$

注意对原始数据的去重与排序。

 1n = map(int, input().strip().split())
 2nums = sorted(list(set(map(int, input().strip().split()))))
 3
 4
 5def gcd(a, b):
 6    return a if b == 0 else gcd(b, a % b)
 7
 8
 9def gcd_sub(x, y):
10    if x > y:
11        x, y = y, x
12    if x == 1:
13        return y
14    return gcd_sub(y // x, x)
15
16
17numes, denos = list(), list()
18nume, deno = -1, -1
19for i in range(1, len(nums)):
20    ni, nj = nums[i - 1 : i + 1]
21    g = gcd(ni, nj)
22    numes.append(nj // g)
23    denos.append(ni // g)
24
25nume, deno = numes[0], denos[0]
26for i in range(1, len(numes)):
27    nume = gcd_sub(nume, numes[i])
28    deno = gcd_sub(deno, denos[i])
29print(f"{nume}/{deno}")

python

辗转相减法具体应用。

1301. C 循环 | 原题链接

这道题和前面的五指山一样，是一道解线性同余方程的问题。令 $K=2^k$ ，此题要解的方程为 $A+Cx\equiv B\space(mod\space K)$ 。剩下的套模板即可。

 1import sys
 2
 3
 4def gcd(a, b):
 5    return a if b == 0 else gcd(b, a % b)
 6
 7
 8def exgcd(a, b):
 9    if b == 0:
10        return 1, 0
11    x, y = exgcd(b, a % b)
12    return y, x - a // b * y
13
14
15data = sys.stdin.read().strip().split("\n")
16for query in data:
17    A, B, C, k = map(int, query.strip().split())
18    if A == B == C == k == 0:
19        break
20
21    K = 2**k
22    if (B - A) % gcd(C, K) != 0:
23        print("FOREVER")
24        continue
25
26    x0, y0 = exgcd(C, K)
27    x = x0 * (B - A) // gcd(C, K)
28    x %= K // gcd(C, K)
29    print(x)

python

1225. 正则问题 | 原题链接

这道题像极了初学栈时做的匹配括号练习题：每读到一个下括号，就往回走到上括号并记录每一段“或”的长度，然后用其中最长的一段覆盖处理完的括号。

 1from collections import deque, defaultdict
 2
 3s = "(" + input().strip() + ")"
 4stack = deque()
 5
 6for c in s:
 7    if c == ")":
 8        segs = defaultdict(int)
 9        seg = 0
10        while stack[-1] != "(":
11            ch = stack.pop()
12            if ch == "|":
13                seg += 1
14            else:
15                segs[seg] += 1
16        stack.pop()
17        length = max(segs.values())
18        for _ in range(length):
19            stack.append("x")
20    else:
21        stack.append(c)
22
23print(len(stack))

python

1303. 斐波那契前 n 项和 | 原题链接

这道题看着不难，但是数据量很大，想要 AC 还是得费点心思。首先是一个最常规的做法：

 1n, m = map(int, input().strip().split())
 2if n == 1:
 3    print(1)
 4    exit()
 5
 6s = 1
 7a, b = 1, 1
 8for _ in range(1, n):
 9    s += b
10    s %= m
11    a, b = b, a + b
12
13print(s % m)

python

可以过 7/13 个测试点。

这道题的正解是使用矩阵快速幂。一般的线性递推关系可以使用矩阵快速幂来求解第 $n$ 项。矩阵快速幂的讲解与例题可见斐波那契数列的矩阵快速幂求法。（矩阵的 Latex 实在不好敲）。

这道题中的“底数矩阵”为：

$\begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix}$

“初始矩阵”为：

$\begin{bmatrix} 1 \\ 1 \\ 1 \\ \end{bmatrix}$

指数为 $n-1$ 。

 1n, m = map(int, input().strip().split())
 2MAT = [[0, 1, 0], [1, 1, 0], [0, 1, 1]]
 3E = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
 4f0 = [[1], [1], [1]]
 5
 6
 7def mat_mul(a, b):
 8    x = len(a)
 9    y = len(b[0])
10    ans = [[0 for _ in range(y)] for _ in range(x)]
11    for i in range(x):
12        for j in range(y):
13            for k in range(len(b)):
14                ans[i][j] += (a[i][k] * b[k][j]) % m
15    return ans
16
17
18n -= 1
19while n:
20    if n & 1:
21        E = mat_mul(MAT, E)
22    MAT = mat_mul(MAT, MAT)
23    n >>= 1
24
25res = mat_mul(E, f0)
26print(res[2][0] % m)

python

每一次矩阵乘法时，都必须将得到的结果对 $m$ 取余以避免运算速度越来越低。

数学与数论类题目练习

文章目录

题目来自 AcWing

1246. 等差数列 | 原题链接

1295. X的因子链 | 原题链接

1296. 聪明的燕姿 | 原题链接

1299. 五指山 | 原题链接

1223. 最大比例 | 原题链接

1301. C 循环 | 原题链接

1225. 正则问题 | 原题链接

1303. 斐波那契前 n 项和 | 原题链接

系列文章