GESP练题小程序艾墨舟编程小先锋专为GESP考生打造的免费题库。涵盖图形化/Python/C++全真题，支持真题模考、考前预测、错题整理与学习统计，一站式攻克客观题。

GESP Python五级2026年3月认证试题解析

1 单选题

---✨ 第1题 ✨--

题目原文关于 Python 实现的单链表、双链表和循环链表，下列说法正确的是（  ）。 A. 在 Python 实现的单链表中，若已知任意结点对象的引用，则可以在 O(1) 时间内删除该结点。 B. Python 实现的循环链表中一定不存在值为 None 的引用属性。 C. 在 Python 实现的循环双链表中，尾结点对象的 next 属性值一定为 None。 D. 在 Python 实现的带头结点的循环单链表中，判定链表是否为空只需判断头结点对象的 next 属性是否引用头结点自身（即 head.next is head）。

考查知识点链表（单链表、双链表、循环链表）的基本概念与操作。

详细解析

答案：D

---✨ 第2题 ✨---

题目原文双向循环链表中要在结点 p 之前插入新结点 s（均非空），以下操作正确的是（   ）。 A.

s.next=p
p.prev=s
q.next=s
s.prev=q

B.

s.prev=p
s.next=p.next
p.next.prev=s
p.next=s

C.

s.next=p
s.prev=p.prev
p.prev.next=s
p.prev=s

D.

s.next=p
s.prev=nullptr
p.prev=s

考查知识点双向循环链表的插入操作。

详细解析在双向循环链表中，在节点 p 之前插入新节点 s，需要修改四个指针：

1. s 的 next 指向 p。
2. s 的 prev 指向 p 原来的前驱节点（即 p.prev）。
3. p 原来前驱节点（p.prev）的 next 指向 s。
4. p 的 prev 指向 s。 操作顺序需注意，避免丢失对原前驱节点的引用。

答案：C

---✨ 第3题 ✨---

题目原文下面函数删除单向链表中 val == x 的节点，并且使用哑结点统一对头结点和中间节点的删除操作。横线处应填（  ）。

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def eraseAll(head, x):
    dummy = Node(0)
    dummy.next = head
    cur = dummy

    while cur.next:
        if cur.next.val == x:
              # 填空处
        else:
            cur = cur.next

    return dummy.next

A. cur = cur.nextB. cur.next = cur.next.nextC. cur.next = NoneD. cur.next = nullptr

考查知识点单链表的删除操作，哑节点（dummy node）技巧。

详细解析函数使用 cur 指针遍历，cur 初始指向哑节点。当 cur.next 的值等于 x 时，需要删除 cur.next 这个节点。删除操作是让 cur.next 跳过该节点，直接指向 cur.next.next。 删除后，cur 指针不应移动，因为新的 cur.next（即原 cur.next.next）可能也需要被删除，需要再次检查。

答案：B

---✨ 第4题 ✨---

题目原文对如下代码实现的欧几里得算法（辗转相除法），调用 gcd(48, 18) 得到的调用序列为（  ）。

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

A. gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)B. gcd(48,18) -> gcd(30,18) -> gcd(12,18)C. gcd(48,18) -> gcd(18,30) -> gcd(30,6)D. gcd(48,18) -> gcd(12,18) -> gcd(6,12)

考查知识点欧几里得算法（辗转相除法）的递归过程。

详细解析算法原理：gcd(a, b) = gcd(b, a % b)，直到 b == 0 时返回 a。 计算 gcd(48, 18)：

• 48 % 18 = 12，所以递归调用 gcd(18, 12)。
• 18 % 12 = 6，所以递归调用 gcd(12, 6)。
• 12 % 6 = 0，所以递归调用 gcd(6, 0)。
• b == 0，返回 a=6。

答案：A

---✨ 第5题 ✨---

题目原文下面代码实现了欧拉（线性）筛，横线处应填写（   ）。

def euler_sieve_for(n):
    if n < 2:
        return []
    is_composite = [False] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)


            p = primes[j]
            if i * p > n:
                break
            is_composite[i * p] = True
            if i % p == 0:
                break
    return primes

A. for j in range(len(primes+1)):B. for j in range(len(primes)+1):C. for j in range(len(primes)):D. for j in range(len(primes)-1):

考查知识点线性筛（欧拉筛）的算法实现。

详细解析线性筛的核心是：对于每个数 i，用当前已知的质数 primes[j] 去标记合数 i * primes[j]，并在 i % primes[j] == 0 时跳出内循环，以确保每个合数只被其最小质因子标记一次。 内循环需要遍历 primes 列表中的所有质数，直到 i * primes[j] > n 或 i % primes[j] == 0。 因此，循环条件应为 for j in range(len(primes)):，即遍历 primes 的每一个索引 j。

答案：C

---✨ 第6题 ✨---

题目原文埃氏筛中将内层循环从 j = ii 开始而不是 j = 2i 的主要原因是（  ）。 A. 因为 2i 一定不是合数 B. ii 一定是质数 C. 小于 i*i 的 i 的倍数已被更小质因子筛过 D. 这样可以把时间复杂度降为 O(n log log n)

考查知识点埃拉托斯特尼筛法（埃氏筛）的优化原理。

详细解析在埃氏筛中，当我们用质数 i 去标记它的倍数时，2*i, 3*i, ... 这些数中，有些可能已经被比 i 更小的质数标记过了。例如，i=5 时，5*2=10 已经被质数2标记过，5*3=15 已经被质数3标记过，5*4=20 已经被质数2标记过。 实际上，对于质数 i，所有小于 i*i 的合数 i * k (其中 k < i) 都已经被小于 i 的质数标记过了（因为 k 有比 i 小的质因子）。因此，从 j = i*i 开始标记，可以避免重复标记，提高效率，但不改变算法的时间复杂度上界。

答案：C

---✨ 第7题 ✨---

题目原文下面程序的运行结果为（  ）。

def check(n, a, k, dist):
    cnt = 1
    last = a[0]

    for i in range(1, n):
        if a[i] - last >= dist:
            cnt += 1
            last = a[i]

    return cnt >= k

def solve(n, a, k):
    a.sort()

    l = 0
    r = a[-1] - a[0]

    while l < r:
        mid = (l + r + 1) // 2
        if check(n, a, k, mid):
            l = mid
        else:
            r = mid - 1

    return l

if __name__ == "__main__":
    a = [1, 2, 8, 4, 9]
    n = 5
    k = 3
    result = solve(n, a, k)
    print(result)

A. 2 B. 3 C. 4 D. 5

考查知识点二分答案算法，贪心验证。

详细解析这是一个典型的“最大化最小距离”问题（类似安排牛舍）。solve 函数对可能的距离 mid 进行二分搜索，check 函数验证是否能在数组中选出至少 k 个点，使得任意两点之间的距离不小于 dist。 验证方法（贪心）：从第一个点开始，依次选择距离上一个被选点至少 dist 的点，统计能选出的点数 cnt。如果 cnt >= k，则 dist 可行。

给定数组 a = [1, 2, 8, 4, 9]，排序后为 [1, 2, 4, 8, 9]，k=3。 二分搜索范围 l=0, r=9-1=8。 我们模拟关键步骤：

• mid = (0+8+1)//2 = 4，check(..., dist=4)：从1开始，下一个>=1+4=5的是8，再下一个>=8+4=12的是？没有。只选出2个点(1,8)，cnt=2<3，不可行。r=mid-1=3。
• mid = (0+3+1)//2 = 2，check(..., dist=2)：从1开始，下一个>=3的是4，再下一个>=6的是8，再下一个>=10的是？没有。选出3个点(1,4,8)，cnt=3>=3，可行。l=mid=2。
• 现在 l=2, r=3，mid = (2+3+1)//2 = 3，check(..., dist=3)：从1开始，下一个>=4的是4，再下一个>=7的是8，再下一个>=11的是？没有。选出3个点(1,4,8)，cnt=3>=3，可行。l=mid=3。
• 现在 l=3, r=3，循环结束，返回 l=3。 所以输出结果为3。

答案：B

---✨ 第8题 ✨---

题目原文在升序数组中查找第一个大于等于x的位置，下面循环中横线应填（  ）。

def lowerBound(a, x):
    l = 0
    r = len(a)
    while l < r:
        mid = l + (r - l) // 2
        if a[mid] >= x:

        else:
            l = mid + 1
    return l

if __name__ == "__main__":
    a1 = [1, 3, 5, 7, 9]
    x1 = 5
    print(f"数组{a1}中第一个 ≥{x1}的位置：{lowerBound(a1, x1)}")

A. r = midB. r = mid - 1C. l = midD. l = mid + 1

考查知识点二分查找（下界查找）。

详细解析这是标准的二分查找下界（lower bound）实现。搜索区间为左闭右开 [l, r)。当 a[mid] >= x 时，说明 mid 位置可能是一个候选答案（或者答案在左边），因此应该将右边界 r 缩小到 mid，以继续在左半部分 [l, mid) 搜索。当 a[mid] < x 时，答案一定在右边，所以 l = mid + 1。 循环结束时 l == r，且 l 就是第一个大于等于 x 的位置。

答案：A

---✨ 第9题 ✨---

题目原文关于递归函数调用，下列说法错误的是（  ）。 A. 递归调用层次过深时，可能会耗尽栈空间导致栈溢出 B. 尾递归函数可以通过编译器优化来避免栈溢出 C. 所有递归函数都可以通过循环结构来改写，从而避免栈溢出 D. 栈溢出发生时，程序会抛出异常并可以继续执行后续代码

考查知识点递归的原理、栈溢出、尾递归优化。

详细解析

答案：D

---✨ 第10题 ✨---

题目原文给定 n 根木头，第 i 根长度为 a[i]。要切成不少于 m 段等长木段，求最大可能长度，则横线上应填写（    ）。

def check(a, m, x):
    cnt = 0
    for length in a:
        if x == 0:
            return True
        cnt += length
        if cnt >= m:
            return True
    return cnt >= m

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    m = int(input[idx])
    idx += 1

    a = []
    mx = 0
    for _ in range(n):
        num = int(input[idx])
        idx += 1
        a.append(num)
        mx = max(mx, num)

    l = 1
    r = mx
    ans = 0

    while l <= r:
        mid = l + (r - l) // 2
        if check(a, m, mid):
            ans = mid
              # 第一空
        else:
              # 第二空

    print(ans)

if __name__ == "__main__":
    main()

A. l = mid + 1 和 r = mid - 1B. r = mid - 1 和 l = mid + 1C. l = mid + 1 和 r = midD. l = mid - 1 和 r = mid + 1

考查知识点二分答案，整数二分模板。

详细解析这是一个“最大化等长木段长度”的问题。check(a, m, x) 函数判断是否能够将木头切成每段长度为 x 的至少 m 段。注意，原 check 函数实现有误，正确的应该是计算每根木头能切出的段数：cnt += length // x。但题目给定了有误的 check 函数，我们只能基于此函数和二分逻辑来推断填空。

二分搜索区间为 [l, r]，闭区间。ans 记录当前可行的最大长度。 当 check 返回 True 时，说明长度 mid 可行，那么可能还有更大的可行长度，所以应该搜索右半部分，即更新 l = mid + 1。同时，用 ans 记录下这个可行的 mid。 当 check 返回 False 时，说明长度 mid 不可行，应该尝试更小的长度，即更新 r = mid - 1。 这是典型的“寻找最大可行解”的二分模板。

答案：A

---✨ 第11题 ✨---

题目原文下面代码用分治求 “最大连续子段和” ，其时间复杂度为（  ）。

import sys

def solve(a, l, r):
    if l == r:
        return a[l]

    mid = l + (r - l) // 2

    left = solve(a, l, mid)
    right = solve(a, mid + 1, r)

    sum_val = 0
    lmax = -sys.maxsize - 1
    for i in range(mid, l - 1, -1):
        sum_val += a[i]
        lmax = max(lmax, sum_val)

    sum_val = 0
    rmax = -sys.maxsize - 1
    for i in range(mid + 1, r + 1):
        sum_val += a[i]
        rmax = max(rmax, sum_val)

    return max(left, right, lmax + rmax)

if __name__ == "__main__":
    a1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(solve(a1, 0, len(a1)-1))

    a2 = [-5, -3, -1, -4]
    print(solve(a2, 0, len(a2)-1))

    a3 = [10]
    print(solve(a3, 0, 0))

A. O(n) B. O(n log n) C. O(n^2) D. O(log n)

考查知识点分治算法的时间复杂度分析。

详细解析这是用分治法求解最大子段和的经典实现。算法将数组分成左右两半，最大子段和要么在左半部分，要么在右半部分，要么跨越中点。递归求解左右两部分，并用 O(n) 的时间计算跨越中点的最大和（即代码中两个循环的部分）。 时间复杂度递推式为：T(n) = 2T(n/2) + O(n)。 根据主定理，该递推式的解为 T(n) = O(n log n)。

答案：B

---✨ 第12题 ✨---

题目原文游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。 A 组：A = {12, 35, 67, 89}， B 组：B = {20, 45, 55, 78}，下面是归并合并函数的核心循环，横线处应填入（  ）。

A = [12, 35, 67, 89]
B = [20, 45, 55, 78]
i = 0
j = 0
result = []
while i < len(A) and j < len(B):
    ————————————————————————
        result.append(A[i])
        i += 1
    else:
        result.append(B[j])
        j += 1
while i < len(A):
    result.append(A[i])
    i += 1
while j < len(B):
    result.append(B[j])
    j += 1
print("合并后的有序排行榜： ", result)

A. if A[i+1] <= B[j]:B. if A[i] <= B[j+1]:C. if A[i] <= B[j]:D. if i < j:

考查知识点归并排序中的合并操作。

详细解析合并两个已排序数组的标准算法是：比较两个数组当前指针所指的元素，将较小的那个放入结果数组，并移动相应指针。 因此，条件应为 if A[i] <= B[j]:。如果 A[i] 小于等于 B[j]，则将 A[i] 加入结果，否则将 B[j] 加入结果。

答案：C

---✨ 第13题 ✨---

题目原文有 5 位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为 pivot 的快速排序，请问此次排序的时间复杂度是（   ）。

def quicksort(a, l, r):
    if l >= r:
        return
    pivot = a[l]
    i, j = l, r

    while i < j:
        while i < j and a[j] >= pivot:
            j -= 1
        while i < j and a[i] <= pivot:
            i += 1
        if i < j:
            a[i], a[j] = a[j], a[i]

    a[l], a[i] = a[i], a[l]
    quicksort(a, l, i - 1)
    quicksort(a, i + 1, r)

if __name__ == "__main__":
    scores = [60, 70, 80, 90, 100]
    print("排序前： ", scores)
    quicksort(scores, 0, len(scores)-1)
    print("排序后： ", scores)  # 输出： [60, 70, 80, 90, 100]

    def quicksort_with_log(a, l, r, depth=0):
        if l >= r:
            return
        print(f"递归深度{depth}，处理区间 [{l},{r}] ，数组：{a[l:r+1]}")
        pivot = a[l]
        i, j = l, r
        while i < j:
            while i < j and a[j] >= pivot: j -= 1
            while i < j and a[i] <= pivot: i += 1
            if i < j: a[i], a[j] = a[j], a[i]
        a[l], a[i] = a[i], a[l]
        quicksort_with_log(a, l, i-1, depth+1)
        quicksort_with_log(a, i+1, r, depth+1)

    scores2 = [60,70,80,90,100]
    print("\n递归过程： ")
    quicksort_with_log(scores2, 0, 4)

A. O(n) B. O(n log n) C. O(n^2) D. O(log n)

考查知识点快速排序的时间复杂度分析，最坏情况。

详细解析题目明确指出数组 [60, 70, 80, 90, 100] 已经从小到大排好序。代码中选择第一个元素作为枢轴（pivot）。对于已排序数组，每次划分枢轴（第一个元素）都是当前区间的最小值，导致划分极度不平衡：左子区间为空，右子区间包含剩余 n-1 个元素。这样递归树会退化成一条链，深度为 n。每次划分需要 O(n) 时间，总时间复杂度为 O(n^2)。

答案：C

---✨ 第14题 ✨---

题目原文下面关于排序算法的描述中，不正确的是 (   ) 。 A. 冒泡排序和插入排序都是稳定的排序算法 B. 快速排序和归并排序都是不稳定的排序算法 C. 冒泡排序和插入排序最好时间复杂度均为 O(n) D. 归并排序在最好、最坏和平均三种情况的时间复杂度均为 O(n log n)

考查知识点排序算法的稳定性与时间复杂度。

详细解析

答案：B

---✨ 第15题 ✨---

题目原文下面代码实现两个整数除法，其中被除数为一个 “大整数” ，用字符串表示，除数是一个小整数，用 int 表示，则横线处应该填写（   ）。

def big_integer_division():
    s, b = input().split()
    b = int(b)

    a = [int(c) for c in s]

    c = []
    rem = 0

    for i in range(len(a)):
        rem = rem * 10 + a[i]
        q = rem // b
        c.append(q)


    pos = 0
    while pos < len(c) - 1 and c[pos] == 0:
        pos += 1

    for i in range(pos, len(c)):
        print(c[i], end='')
    print()

    print(rem)

if __name__ == "__main__":
    big_integer_division()

A. rem =rem / bB. rem = rem % bC. rem = bD. rem = q

考查知识点高精度除法（大整数除以小整数）的模拟过程。

详细解析这是模拟手工除法的过程。rem 表示当前的余数。对于被除数的每一位 a[i]，将余数乘以10再加上这一位，得到新的被除数 rem。计算商 q = rem // b，记录到结果 c 中。然后，更新余数 rem 为 rem % b，作为下一位计算的起点。 因此，横线处应填入 rem = rem % b。

答案：B

2 判断题

---✨ 第1题 ✨---

题目原文有一个存储了 n 个整数的线性表，分别用 Python 列表（数组）和自定义单链表两种方式实现。在已知元素下标（或结点对象引用）的前提下， Python 列表的随机访问操作时间复杂度为 O(1) ；而在 Python 实现的单链表中，已知某结点对象的引用时，在该结点之后插入一个新结点的操作时间复杂度也为 O(1) 。

选项

• 正确
• 错误

考查知识点Python列表（动态数组）与单链表的时间复杂度对比。

详细解析

答案：正确

---✨ 第2题 ✨---

题目原文若数组 a 已按升序排列，则下面代码可以正确实现 “在 a 中查找第一个大于等于 x 的元素的位置” 。

def lowerBound(a, x):
    l = 0
    r = len(a)
    while l < r:
        mid = (l + r) // 2
        if a[mid] >= x:
            r = mid
        else:
            l = mid + 1
    return l

if __name__ == "__main__":
    a1 = [1, 3, 5, 7, 9]
    x1 = 5
    print(f"数组{a1}中第一个 ≥{x1}的位置：{lowerBound(a1, x1)}")
    x2 = 6
    print(f"数组{a1}中第一个 ≥{x2}的位置：{lowerBound(a1, x2)}")
    x3 = 10
    print(f"数组{a1}中第一个 ≥{x3}的位置：{lowerBound(a1, x3)}")
    x4 = 0
    print(f"数组{a1}中第一个 ≥{x4}的位置：{lowerBound(a1, x4)}")

选项

• 正确
• 错误

考查知识点二分查找下界（lower bound）的实现。

详细解析

答案：正确

---✨ 第3题 ✨---

题目原文快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。

选项

• 正确
• 错误

考查知识点快速排序的稳定性。

详细解析

答案：错误

---✨ 第4题 ✨---

题目原文若某算法满足递推式：T(n) = 2T(n/2) + O(n)，则其时间复杂度为 O(n log n)。

选项

• 正确
• 错误

考查知识点递归式的时间复杂度分析（主定理）。

详细解析

答案：正确

---✨ 第5题 ✨---

题目原文在一个数组中，如果两个元素 a[i] 和 a[j]满足 i < j 且 a[i] > a[j]，则 a[i] 和 a[j]是一个逆序对。 下面代码可以正确统计数组 a 区间 [l,r] 内的逆序对总数。

cnt = 0
def merge_count(a, l, m, r):
    global cnt
    i = l
    j = m + 1

    while i <= m and j <= r:
        if a[i] <= a[j]:
            i += 1
        else:
            cnt += (m - i + 1)
            j += 1

if __name__ == "__main__":
    a = [2, 4, 1, 3]
    merge_count(a, 0, 1, 3)
    print(f"跨区间逆序对数量：{cnt}")

选项

• 正确
• 错误

考查知识点逆序对的定义及归并排序统计逆序对的方法。

详细解析

答案：错误

---✨ 第6题 ✨---

题目原文唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。

选项

• 正确
• 错误

考查知识点质数判定与唯一分解定理。

详细解析

答案：正确

---✨ 第7题 ✨---

题目原文假设数组 a 的值域范围是 [1, n]，以下程序的时间复杂度是 O(n)。

def check(n, a, k, dist):
    cnt = 1
    last = a[0]

    for i in range(1, n):
        if a[i] - last >= dist:
            cnt += 1
            last = a[i]

    return cnt >= k

def solve(n, a, k):
    a_sorted = a.copy()
    a_sorted.sort()

    l = 0
    r = a_sorted[-1] - a_sorted[0]

    while l < r:
        mid = (l + r + 1) // 2
        if check(n, a_sorted, k, mid):
            l = mid
        else:
            r = mid - 1

    return l

if __name__ == "__main__":
    a = [1, 2, 8, 4, 9]
    n = 5
    k = 3
    result = solve(n, a, k)
    print(result)

选项

• 正确
• 错误

考查知识点算法时间复杂度分析，二分答案。

详细解析

答案：错误

---✨ 第8题 ✨---

题目原文若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。（  ）

选项

• 正确
• 错误

考查知识点贪心算法与最优子结构。

详细解析

答案：错误

---✨ 第9题 ✨---

题目原文线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过 "每个合数只被其最大质因子筛去" 的策略，保证每个合数恰好被标记一次，从而实现 O(n) 的时间复杂度。

选项

• 正确
• 错误

考查知识点线性筛（欧拉筛）的原理。

详细解析

答案：正确

---✨ 第10题 ✨---

题目原文任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。

选项

• 正确
• 错误

考查知识点递归与非递归的转换。

详细解析

答案：错误

3 编程题

3.1 编程题 1：有限不循环小数

题目描述若 a/b 可化为一个有限的，不循环的小数，则称 a/b 为终止数。 请你求出在 L 到 R 中终止数的数量。

输入格式输入一行，包含两个整数 L, R。

输出格式输出一行，包含一个整数，表示 L 到 R 中终止数的数量。

样例输入

2 11

样例输出

5

样例解释在 2 到 11 终止数有 2, 4, 5, 8, 10。

数据范围保证 1 <= L <= R <= 10^6。

考查知识点数学知识：一个最简分数能化为有限小数的充要条件是分母的质因数只包含2和5。

解题思路

1. 题目本质是求区间 [L, R] 内，有多少个数 a，使得存在某个 b，a/b 是有限小数。但题目描述可能引起歧义。更常见的理解是：对于一个分数 a/b，当它化为最简分数后，若分母的质因数只有2和5，则该分数可以化为有限小数。但题目中“在 L 到 R 中终止数的数量”可能指的是分子 a 在区间 [L, R] 内，且分母 b 任意？这会导致无限多个。结合样例，2到11中终止数有5个：2,4,5,8,10。这些数恰好是质因数只包含2和5的数（1也满足，但不在区间内）。
2. 因此，合理的解释是：题目问的是区间 [L, R] 内，其质因数只包含2和5的正整数的个数。这样的数可以写成 2^p * 5^q 的形式（p,q >=0）。
3. 算法：遍历区间内每个数，不断除以2，再不断除以5，如果最终剩下1，说明该数质因数只有2和5，计数加一。
4. 复杂度：对于每个数，除法操作次数有限，总复杂度 O((R-L+1) * log R)，在数据范围内可行。

参考程序解析

# L ， R 输入
l, r = map(int, input().split())
# 最终的答案，初始化为 0
ans = 0
for i in range(l, r + 1):
    t = i
    # 不断除以 2
    while t > 0 and t % 2 == 0:
        t //= 2
    # 不断除以 5
    while t > 0 and t % 5 == 0:
        t //= 5
    # 如果不含其他因子，则这个数能够表示为不循环的小数
    if t == 1:
        ans += 1
print(ans)

3.2 编程题 2：找数

题目描述给定一个包含 n 个互不相同的正整数的数组 a 与一个包含 m 个互不相同的正整数的数组 b ，请你帮忙计算有多少数在数组 a 与 数组 b 中均出现。

输入格式第一行包含两个整数 n, m。 第二行包含 n 个正整数 a_i 表示数组 a。 第三行包含 m 个正整数 b_i 表示数组 b。

输出格式输出一个整数，表示在数组 a 与 数组 b 中均出现的数的个数。

样例输入

3 5
4 2 3
3 1 5 4 6

样例输出

2

样例解释样例 1 中，3、4 在数组 a 与 b 中均出现。

数据范围对于 30% 的数据，保证 n, m <= 1000。 对于 100% 的数据，保证 n, m <= 10^5，1 <= a_i, b_i <= 10^9。

考查知识点查找、二分查找或集合（哈希集合）。

解题思路

1. 求两个数组的交集元素个数。
2. 由于数组元素互不相同，且数据规模较大（10^5），需要高效算法。
3. 方法一：将数组 a 排序，然后对于数组 b 中的每个数，在排序后的 a 中使用二分查找判断是否存在。时间复杂度 O(n log n + m log n)。
4. 方法二：使用 Python 的集合（set）。将数组 a 转换为集合，然后遍历数组 b，判断元素是否在集合中。集合查找平均 O(1)，总时间复杂度 O(n + m)。在 Python 中这种方法更简洁高效。

参考程序解析参考程序使用了二分查找的方法。

# 接收 a,b 数组的大小以及数组内容
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()  # 对 a 排序，便于二分查找
ans = 0
# 遍历 b 中的每一个数
for x in b:
    l, r = 0, n - 1
    # 二分查找 a 中是否包含 x
    while l < r:
        mid = (l + r) // 2
        # 如果 a[mid]<x ，则 x 一定在 mid+1 之后
        if a[mid] < x:
            l = mid + 1
        else:
            r = mid
    if a[l] == x:
        ans += 1
print(ans)

也可以使用集合实现：

n, m = map(int, input().split())
a = set(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
for x in b:
    if x in a:
        ans += 1
print(ans)