✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

小红书-2026.03.11

本次三题均对应历史原题，红薯已经连续好几场是这样了

题目一：完美数字

这题的关键在于满足条件的连续正整数乘积其实非常少，可以先把所有合法答案一次性预处理出来，之后每次询问直接判断是否命中即可。

难度：Mid

题目二：小毛的收藏品评估系统

题目的本质是统计数组中与查询值存在整除关系的元素个数。做法上可以先用筛法预处理“因子贡献”和“倍数贡献”，这样单次查询就能做到常数时间回答。

难度：Mid

题目三：小毛的古籍修复

把所有已知位置之间的缺失段拆开后，每一段都可以转化成一个非降序列填数方案计数问题，本质上是标准的多重组合计数，最后把各段答案相乘即可。

难度：High

01. 完美数字

问题描述

本题是小红书 2025.08.27 第 1 题的原题。

用户的每一次点赞都代表着对内容的喜爱。小红定义一个正整数 为完美数字，当且仅当同时满足以下两个条件：

• 可以将 写作一个公差为 且所有元素都是正整数的等差数列的乘积，例如， 可以写作 ；

• 上述等差数列的长度至少为 。

现在小红薯接收到多次 点赞数查询，每次给出一个正整数 ，请帮助小红薯判断该点赞数是否为完美数字。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数。

接下来每组测试数据输入一行，一个整数 ，表示一次点赞数查询。

输出格式

对于每组测试数据，新起一行，如果点赞数是完美数字，输出 YES；否则，输出 NO。

样例输入

3
6
2
24

样例输出

YES
NO
YES

数据范围

• 
• 

题解

这题如果对每个询问都临时去试所有长度和起点，思路当然也能写，但完全没有必要。真正该抓住的是上界：，满足条件的连续乘积总数其实非常少，完全可以一次性预处理出来。

设一个完美数字写成：

其中 ，。

先看长度上界。若 ，最小乘积都已经是：

所以合法长度只可能在 之间，长度范围一下子就被压得很小了。

接着枚举每个长度 的起点 。因为乘积会随着 的增大快速变大，所以一旦某个起点已经越界，后面的起点也不用再试。这样预处理下来，所有可能的完美数字只有很少一批，直接塞进哈希表即可。

之后每次询问只需要判断这个数在不在集合里，单次复杂度就是 。

复杂度方面：

• 预处理总规模很小，可以认为是常数级。
• 每次查询时间复杂度是 。

参考代码

• Python

import sys

input = lambda: sys.stdin.readline().strip()

LIM = 10 ** 9
good = set()

for length in range(3, 13):
    start = 1
    while True:
        prod = 1
        overflow = False
        for offset in range(length):
            value = start + offset
            # 先判断这一位乘上去会不会越界。
            if prod > LIM // value:
                overflow = True
                break
            prod *= value
        # 当前起点已经越界，后面的起点只会更大。
        if overflow:
            break
        good.add(prod)
        start += 1


def solve():
    t = int(input())
    for _ in range(t):
        x = int(input())
        # 预处理后，每次询问只要查集合。
        print('YES' if x in good else 'NO')


if __name__ == '__main__':
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const long long lim = 1000000000LL;
    unordered_set<long long> good;

    for (int len = 3; len <= 12; ++len) {
        for (long long start = 1; ; ++start) {
            long long prod = 1;
            bool overflow = false;

            for (int offset = 0; offset < len; ++offset) {
                long long value = start + offset;
                // 先判断这一位乘上去会不会越界。
                if (prod > lim / value) {
                    overflow = true;
                    break;
                }
                prod *= value;
            }

            // 当前起点已经越界，后面的起点也不用再试。
            if (overflow) {
                break;
            }
            good.insert(prod);
        }
    }

    int t;
    cin >> t;
    while (t--) {
        long long x;
        cin >> x;
        // 预处理后，单次查询就是 O(1) 查表。
        cout << (good.count(x) ? "YES" : "NO") << '\n';
    }
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        final long lim = 1000000000L;
        Set<Long> good = new HashSet<>();

        for (int len = 3; len <= 12; len++) {
            for (long start = 1; ; start++) {
                long prod = 1;
                boolean overflow = false;

                for (int offset = 0; offset < len; offset++) {
                    long value = start + offset;
                    // 先判断这一位乘上去会不会越界。
                    if (prod > lim / value) {
                        overflow = true;
                        break;
                    }
                    prod *= value;
                }

                // 当前起点已经越界，后面的起点也不用再试。
                if (overflow) {
                    break;
                }
                good.add(prod);
            }
        }

        int t = Integer.parseInt(br.readLine());
        StringBuilder ans = new StringBuilder();
        while (t-- > 0) {
            long x = Long.parseLong(br.readLine());
            // 预处理后，每次询问就是查集合。
            ans.append(good.contains(x) ? "YES" : "NO").append('\n');
        }
        System.out.print(ans);
    }
}

02. 小毛的收藏品评估系统

问题描述

本题是小红书 2025.08.24-第一套 第 2 题的原题。

小毛是一位古董收藏家，他建立了一个收藏品评估系统。在这个系统中，每件收藏品都有一个唯一的价值评分。

系统中定义两件收藏品为"兼容品"，当且仅当其中一件收藏品的价值评分能够被另一件的价值评分整除（即两个评分之间存在整除关系）。

现在小毛的数据库中存储了 件收藏品的价值评分。接下来会进行 次查询，每次查询给出一个新收藏品的价值评分 ，请你帮助小毛统计数据库中有多少件收藏品与这个新收藏品是"兼容品"。

输入格式

第一行输入两个整数 （），分别表示数据库中收藏品的数量和查询次数。

第二行输入 个整数 （），表示数据库中每件收藏品的价值评分。

接下来 行，每行输入一个整数 （），表示一个新收藏品的价值评分。

输出格式

对于每次查询，输出一个整数，表示数据库中与查询的收藏品为"兼容品"的收藏品数量。

样例输入

5 3
1 2 2 5 6
4
2
1

样例输出

3
4
5

数据范围

• 
• 

样例	解释说明
样例1查询	数据库中的（因为）、（因为）、（因为）与兼容，共件
样例2查询	数据库中的（因为）、（因为）、（因为）、（因为）与兼容，共件
样例3查询	数据库中所有收藏品都与兼容（因为能整除所有正整数），共件

题解

两个人能构成“同好”，等价于两人的分数存在整除关系。

对于一次查询给定 ，答案由两部分组成：

• 数据库里所有能整除 的数；
• 数据库里所有能被 整除的数。

如果某个数刚好等于 ，它会同时落在这两部分里，所以最后还要减去一次 cnt[x] 去重。

预处理什么

设 cnt[v] 表示数据库里值为 的人数。

我们希望把每个可能的查询值 的答案都先算出来。

记：

• div_cnt[x]：数据库中有多少数是 的因子；
• mul_cnt[x]：数据库中有多少数是 的倍数。

那么：

怎么筛出来

枚举一个值 d，如果数据库里它出现了 cnt[d] 次，那么：

• 对于所有 d 的倍数 mult，d 都是 mult 的因子，所以 div_cnt[mult] += cnt[d]；
• 同时对于这个 d 自己来说，所有这些 mult 都是它的倍数，所以 mul_cnt[d] += cnt[mult]。

也就是说，只要枚举 d 和它的所有倍数，就能把两类统计一起做完。这和筛法的遍历方式完全一致，总复杂度是调和级数：

这里 ，完全可以接受。

复杂度分析

• 预处理 cnt 需要 ；
• 枚举所有整除关系需要 ；
• 每次查询直接输出预处理结果，复杂度 。

总复杂度为 ，额外空间复杂度为 。

参考代码

• Python

import sys

input = lambda: sys.stdin.readline().strip()
MAXV = 500000


def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    cnt = [0] * (MAXV + 1)
    for value in a:
        # 统计数据库中每个分数出现了多少次。
        cnt[value] += 1

    div_cnt = [0] * (MAXV + 1)
    mul_cnt = [0] * (MAXV + 1)

    for d in range(1, MAXV + 1):
        # 枚举 d 的所有倍数 mult。
        for mult in range(d, MAXV + 1, d):
            # d 是 mult 的因子。
            div_cnt[mult] += cnt[d]
            # mult 是 d 的倍数。
            mul_cnt[d] += cnt[mult]

    ans = [0] * (MAXV + 1)
    for x in range(1, MAXV + 1):
        # 等于 x 的人会在因子和倍数两部分各算一次，需要去重。
        ans[x] = div_cnt[x] + mul_cnt[x] - cnt[x]

    out = []
    for _ in range(m):
        x = int(input())
        out.append(str(ans[x]))
    sys.stdout.write('\n'.join(out))


if __name__ == '__main__':
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

static const int MAXV = 500000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> cnt(MAXV + 1, 0);
    for (int i = 0; i < n; ++i) {
        int value;
        cin >> value;
        // 统计数据库中每个分数出现了多少次。
        ++cnt[value];
    }

    vector<int> divCnt(MAXV + 1, 0), mulCnt(MAXV + 1, 0), ans(MAXV + 1, 0);

    for (int d = 1; d <= MAXV; ++d) {
        // 枚举 d 的所有倍数 mult。
        for (int mult = d; mult <= MAXV; mult += d) {
            // d 是 mult 的因子。
            divCnt[mult] += cnt[d];
            // mult 是 d 的倍数。
            mulCnt[d] += cnt[mult];
        }
    }

    for (int x = 1; x <= MAXV; ++x) {
        // 等于 x 的人会在因子和倍数两部分各算一次，需要去重。
        ans[x] = divCnt[x] + mulCnt[x] - cnt[x];
    }

    while (m--) {
        int x;
        cin >> x;