🔗刷题网址: bishipass.com# 小红书-2026.03.11
本次三题均对应历史原题，红薯已经连续N场是这样了
题目一：完美数字
这题的关键在于满足条件的连续正整数乘积其实非常少，可以先把所有合法答案一次性预处理出来，之后每次询问直接判断是否命中即可。
难度：Mid
题目二：A先生的收藏品评估系统
题目的本质是统计数组中与查询值存在整除关系的元素个数。做法上可以先用筛法预处理“因子贡献”和“倍数贡献”，这样单次查询就能做到常数时间回答。
难度：Mid
题目三：A先生的古籍修复
把所有已知位置之间的缺失段拆开后，每一段都可以转化成一个非降序列填数方案计数问题，本质上是标准的多重组合计数，最后把各段答案相乘即可。
难度：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
whileTrue:
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
defsolve():
t = int(input())
for _ in range(t):
x = int(input())
# 预处理后，每次询问只要查集合。
print('YES'if x in good else'NO')
if __name__ == '__main__':
solve()
- >
Cpp
#include
usingnamespacestd;
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
constlonglong lim = 1000000000LL;
unordered_set good;
for (int len = 3; len <= 12; ++len) {
for (longlong start = 1; ; ++start) {
longlong prod = 1;
bool overflow = false;
for (int offset = 0; offset < len; ++offset) {
longlong value = start + offset;
// 先判断这一位乘上去会不会越界。
if (prod > lim / value) {
overflow = true;
break;
}
prod *= value;
}
// 当前起点已经越界，后面的起点也不用再试。
if (overflow) {
break;
}
good.insert(prod);
}
}
int t;
cin >> t;
while (t--) {
longlong x;
cin >> x;
// 预处理后，单次查询就是 O(1) 查表。
cout << (good.count(x) ? "YES" : "NO") << '\n';
}
return0;
}
- >
Java
import java.io.*;
import java.util.*;
publicclassMain{
publicstaticvoidmain(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
finallong lim = 1000000000L;
Set 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. A先生的收藏品评估系统
问题描述
本题是小红书 2025.08.24-第一套 第 2 题的原题。
A先生是一位古董收藏家，他建立了一个收藏品评估系统。在这个系统中，每件收藏品都有一个唯一的价值评分。
系统中定义两件收藏品为"兼容品"，当且仅当其中一件收藏品的价值评分能够被另一件的价值评分整除（即两个评分之间存在整除关系）。
现在A先生的数据库中存储了 件收藏品的价值评分。接下来会进行 次查询，每次查询给出一个新收藏品的价值评分 ，请你帮助A先生统计数据库中有多少件收藏品与这个新收藏品是"兼容品"。
输入格式
第一行输入两个整数 （），分别表示数据库中收藏品的数量和查询次数。
第二行输入 个整数 （），表示数据库中每件收藏品的价值评分。
接下来 行，每行输入一个整数 （），表示一个新收藏品的价值评分。
输出格式
对于每次查询，输出一个整数，表示数据库中与查询的收藏品为"兼容品"的收藏品数量。
样例输入
5 3
1 2 2 5 6
4
2
1
样例输出
3
4
5
数据范围
- >
- >
题解
两个人能构成“同好”，等价于两人的分数存在整除关系。
对于一次查询给定 ，答案由两部分组成：
- >
数据库里所有能整除 的数； - >
数据库里所有能被 整除的数。
如果某个数刚好等于 ，它会同时落在这两部分里，所以最后还要减去一次 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
defsolve():
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
usingnamespacestd;
staticconstint MAXV = 500000;
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vectorcnt(MAXV + 1, 0);
for (int i = 0; i < n; ++i) {
int value;
cin >> value;
// 统计数据库中每个分数出现了多少次。
++cnt[value];
}
vectordivCnt(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;
cout << ans[x] << '\n';
}
return0;
}
- >
Java
import java.io.*;
import java.util.*;
publicclassMain{
staticfinalint MAXV = 500000;
publicstaticvoidmain(String[] args)throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int m = fs.nextInt();
int[] cnt = newint[MAXV + 1];
for (int i = 0; i < n; i++) {
int value = fs.nextInt();
// 统计数据库中每个分数出现了多少次。
cnt[value]++;
}
int[] divCnt = newint[MAXV + 1];
int[] mulCnt = newint[MAXV + 1];
int[] ans = newint[MAXV + 1];
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];
}
StringBuilder out = new StringBuilder();
while (m-- > 0) {
int x = fs.nextInt();
out.append(ans[x]).append('\n');
}
System.out.print(out);
}
staticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buffer = newbyte[1 << 16];
privateint ptr = 0, len = 0;
FastScanner(InputStream is) {
in = is;
}
privateintread()throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buffer[ptr++];
}
intnextInt()throws IOException {
int c;
do {
c = read();
} while (c <= ' ');
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int val = 0;
while (c > ' ') {
val = val * 10 + c - '0';
c = read();
}
return val * sign;
}
}
}
03. A先生的古籍修复
问题描述
本题是小红书 2025.08.13 第 3 题的原题。
A先生是一位古籍修复专家，最近他在修复一本古代数学典籍。这本典籍记录了一个长度为 的数字序列 ，该序列具有非严格递增的特性，即 。
由于年代久远，典籍中部分数字已经模糊不清，A先生用 来表示这些缺失的数字。题目保证序列的第一个数字 和最后一个数字 都是清晰可见的（不为 ）。
A先生需要确定有多少种方式可以填补这些缺失的数字，使得整个序列仍然保持非严格递增的性质。由于方案数可能非常大，请将结果对 取模后输出。
输入格式
第一行包含一个正整数 （），表示序列的长度。
第二行包含 个非负整数 （），其中 表示该位置的数字缺失，其余位置满足非严格递增关系。
输出格式
输出一个整数，表示符合条件的填补方案数对 取模后的结果。
样例输入
3
1 0 5
样例输出
5
数据范围
- >
- >
- >
题解
把所有已知的非零位置拿出来，问题就被分成了若干段互不影响的区间。
设相邻两个已知位置分别是 left 和 right，对应的值是 和 ，它们中间有 gap 个丢失位置。
因为最终数组必须非严格递增，所以这 gap 个位置要填成：
如果某一段出现 ，那说明已知值本身就已经破坏了单调性，答案直接是 。
#一段区间有多少种填法
把每个待填的数都减去左端点 ，记成：
那么条件就变成：
也就是要从区间 里选出 gap 个数，允许重复，最后按不降顺序摆放。
这正是一个标准的可重复组合问题，方案数为：
所以整道题的答案，就是每一段区间方案数的乘积。
#组合数怎么计算
模数 是质数。虽然组合数上面的 n 可能很大，因为 最多到 ，但下面的 k=gap 的总和不超过整个数组长度 。
因此可以只预处理到 的阶乘和逆阶乘，然后用：
分子循环乘 k 次，分母用逆元处理，就能在线性总复杂度内做完。
#复杂度分析
- >
扫描数组并分段：； - >
所有区间里分子连乘的总次数也是 ； - >
额外空间复杂度为 。
总时间复杂度是 。
参考代码
- >
Python
import sys
input = lambda: sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
defmod_pow(base, exp):
result = 1
while exp > 0:
if exp & 1:
result = result * base % MOD
base = base * base % MOD
exp >>= 1
return result
defsolve():
n = int(input())
a = [0] + list(map(int, input().split()))
pos = []
for i in range(1, n + 1):
if a[i] != 0:
pos.append(i)
for i in range(1, len(pos)):
# 已知值本身不满足非严格递增，直接无解。
if a[pos[i - 1]] > a[pos[i]]:
print(0)
return
fac = [1] * (n + 1)
ifac = [1] * (n + 1)
for i in range(1, n + 1):
fac[i] = fac[i - 1] * i % MOD
ifac[n] = mod_pow(fac[n], MOD - 2)
for i in range(n, 0, -1):
ifac[i - 1] = ifac[i] * i % MOD
defcomb_large(total, choose):
if choose < 0or total < choose:
return0
numerator = 1
for i in range(choose):
# 按公式连乘 total * (total-1) * ... * (total-choose+1)。
numerator = numerator * ((total - i) % MOD) % MOD
return numerator * ifac[choose] % MOD
ans = 1
for i in range(len(pos) - 1):
left_pos = pos[i]
right_pos = pos[i + 1]
gap = right_pos - left_pos - 1
if gap == 0:
continue
left_val = a[left_pos]
right_val = a[right_pos]
ways = comb_large(right_val - left_val + gap, gap)
ans = ans * ways % MOD
print(ans)
if __name__ == '__main__':
solve()
- >
Cpp
#include
usingnamespacestd;
constlonglong MOD = 1000000007LL;
longlongmodPow(longlong base, longlongexp){
longlong result = 1;
while (exp > 0) {
if (exp & 1LL) {
result = result * base % MOD;
}
base = base * base % MOD;
exp >>= 1;
}
return result;
}
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vectora(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
vector pos;
for (int i = 1; i <= n; ++i) {
if (a[i] != 0) {
pos.push_back(i);
}
}
for (int i = 1; i < (int)pos.size(); ++i) {
// 已知值本身不满足非严格递增，直接无解。
if (a[pos[i - 1]] > a[pos[i]]) {
cout << 0 << '\n';
return0;
}
}
vectorfac(n + 1), ifac(n + 1);
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % MOD;
}
ifac[n] = modPow(fac[n], MOD - 2);
for (int i = n; i >= 1; --i) {
ifac[i - 1] = ifac[i] * i % MOD;
}
auto combLarge = [&](longlong total, int choose) {
if (choose < 0 || total < choose) {
return0LL;
}
longlong numerator = 1;
for (int i = 0; i < choose; ++i) {
// 按公式连乘 total * (total-1) * ... * (total-choose+1)。
numerator = numerator * ((total - i) % MOD) % MOD;
}
return numerator * ifac[choose] % MOD;
};
longlong ans = 1;
for (int i = 0; i + 1 < (int)pos.size(); ++i) {
int leftPos = pos[i];
int rightPos = pos[i + 1];
int gap = rightPos - leftPos - 1;
if (gap == 0) {
continue;
}
longlong leftVal = a[leftPos];
longlong rightVal = a[rightPos];
longlong ways = combLarge(rightVal - leftVal + gap, gap);
ans = ans * ways % MOD;
}
cout << ans << '\n';
return0;
}
- >
Java
import java.io.*;
import java.util.*;
publicclassMain{
staticfinallong MOD = 1000000007L;
staticlongmodPow(long base, long exp){
long result = 1;
while (exp > 0) {
if ((exp & 1L) != 0) {
result = result * base % MOD;
}
base = base * base % MOD;
exp >>= 1;
}
return result;
}
publicstaticvoidmain(String[] args)throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
long[] a = newlong[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = fs.nextLong();
}
ArrayList pos = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (a[i] != 0) {
pos.add(i);
}
}
for (int i = 1; i < pos.size(); i++) {
// 已知值本身不满足非严格递增，直接无解。
if (a[pos.get(i - 1)] > a[pos.get(i)]) {
System.out.println(0);
return;
}
}
long[] fac = newlong[n + 1];
long[] ifac = newlong[n + 1];
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i % MOD;
}
ifac[n] = modPow(fac[n], MOD - 2);
for (int i = n; i >= 1; i--) {
ifac[i - 1] = ifac[i] * i % MOD;
}
long ans = 1;
for (int i = 0; i + 1 < pos.size(); i++) {
int leftPos = pos.get(i);
int rightPos = pos.get(i + 1);
int gap = rightPos - leftPos - 1;
if (gap == 0) {
continue;
}
long total = a[rightPos] - a[leftPos] + gap;
long numerator = 1;
for (int j = 0; j < gap; j++) {
// 按公式连乘 total * (total-1) * ... * (total-gap+1)。
numerator = numerator * ((total - j) % MOD) % MOD;
}
long ways = numerator * ifac[gap] % MOD;
ans = ans * ways % MOD;
}
System.out.println(ans);
}
staticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buffer = newbyte[1 << 16];
privateint ptr = 0, len = 0;
FastScanner(InputStream is) {
in = is;
}
privateintread()throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buffer[ptr++];
}
intnextInt()throws IOException {
int c;
do {
c = read();
} while (c <= ' ');
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int val = 0;
while (c > ' ') {
val = val * 10 + c - '0';
c = read();
}
return val * sign;
}
longnextLong()throws IOException {
int c;
do {
c = read();
} while (c <= ' ');
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
long val = 0;
while (c > ' ') {
val = val * 10 + c - '0';
c = read();
}
return sign == 1 ? val : -val;
}
}
}
✨ 写在最后：
网站最近上线了八股和选额的功能啦。
最近卡片刷题已经全员开放了，八股和选择题都能直接刷。 我自己还挺喜欢这种刷法的，先看题、自己想，再翻面看答案，会比一直往下看题库更有“在准备面试”的感觉一点。 如果你最近也在刷八股，准备面试、可以来bishipass试试看哦。
文章来源：
四季读书网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至23467321@qq.com举报，一经查实，本站将立刻删除;如已特别标注为本站原创文章的，转载时请以链接形式注明文章出处，谢谢！
