大厂真题 / 蔚来

蔚来 7.26 笔试真题 - 通用岗

本场考试概述

考试时间：2026年7月26日

考试岗位：通用岗

难度评级：中等偏易

考点分析：

• 第一题：阶乘预处理与完全平方数判定（难度中等）
• 第二题：裴蜀定理与区间倍数计数（难度简单）

建议策略：

• 第一题先利用阶乘增长极快的特点缩小枚举范围，再用整数平方根精确判定
• 第二题认出整数线性组合的可表示集合由最大公约数决定，直接计算区间内倍数个数
• 两题都偏数论，重点是把数学结论转成边界正确的 ACM 代码

题目根据公开笔试资料整理，表述与代码均已重新组织。原始资料中的部分公式以 SVG 渲染，本文结合上下文和样例改写为显式数学表达。

第 1 题：阶乘平方数

题目描述

给定一个正整数上界 $n$，找出所有正整数 $x$，使得：

1. $x!+1\le n$；
2. $x!+1$ 是完全平方数。

按从小到大的顺序输出所有满足条件的 $x$。如果不存在，输出 -1。

第一行输入查询次数 $T$，之后每行给出一组查询的 $n$。公开样例覆盖到 $10^{18}$，因此实现按 $n\le 10^{18}$ 处理。

样例

输入

3
1
25
5041

输出

-1
4
4 5 7

输入

2
121
1000000000000000000

输出

4 5
4 5 7

样例解释

$4!+1=25=5^2$，$5!+1=121=11^2$，$7!+1=5041=71^2$，所以当上界达到对应数值时，答案依次包含 $4$、$5$ 和 $7$。

思路分析

第一步：利用阶乘增长缩小范围

直接对每个查询从 $1$ 枚举到 $n$ 没有必要。阶乘增长很快，在 $10^{18}$ 范围内只需检查很少的 $x$。所有查询使用同一组候选，因此可以统一预处理。

第二步：逐项维护阶乘

从 $x=1$ 开始维护 factorial = x!。每得到一个新的阶乘，就计算 value = factorial + 1。如果 value 已超过 $10^{18}$，后续阶乘只会更大，可以停止。

第三步：精确判断完全平方数

浮点数开平方在大整数附近可能产生舍入误差。Python 的 math.isqrt(value) 会返回精确的整数平方根下取整。令 $r=\lfloor\sqrt{value}\rfloor$，只需检查 $r^2=value$。

第四步：回答每组查询

预处理结果按 $x!+1$ 递增保存。对每个 $n$，依次取出数值不超过 $n$ 的 $x$；遇到第一个超出上界的候选即可停止。

正确性说明

预处理按照 $x=1,2,3,\ldots$ 依次计算每个不超过上界的 $x!+1$，因此不会遗漏任何可能的 $x$。isqrt 检查等价于判断该值是否存在整数平方根，所以保存的候选全部满足完全平方条件。查询时仅保留 $x!+1\le n$ 的候选，恰好得到该查询的全部答案。

题解代码

import sys
from math import isqrt

input = sys.stdin.readline
LIMIT = 10**18


def build_candidates():
    candidates = []
    factorial = 1
    x = 1

    while True:
        factorial *= x
        value = factorial + 1
        if value > LIMIT:
            break

        root = isqrt(value)
        if root * root == value:
            candidates.append((value, x))
        x += 1

    return candidates


def solve():
    candidates = build_candidates()
    t = int(input())
    answers = []

    for _ in range(t):
        n = int(input())
        hits = []
        for value, x in candidates:
            if value > n:
                break
            hits.append(str(x))
        answers.append(" ".join(hits) if hits else "-1")

    print("\n".join(answers))


solve()

复杂度分析

时间复杂度：预处理为 $O(K)$，每组查询为 $O(K)$，其中 $K$ 是满足 $x!+1\le 10^{18}$ 的候选枚举数量，实际为很小的常数。

空间复杂度：$O(K)$，用于保存预处理得到的候选。

易错点

• 不要使用浮点 sqrt 直接判断大整数是否为完全平方数
• 查询比较的是 $x!+1$ 与 $n$，而不是 $x$ 与 $n$
• 没有答案时必须输出 -1

第 2 题：线性组合计数

题目描述

给定正整数 $x$、$y$、$l$、$r$，统计闭区间 $[l,r]$ 内有多少个整数 $k$ 可以表示为

其中 $a$、$b$ 可以取任意整数，包括负数和零。

第一行输入查询次数 $T$，之后每行输入四个整数 x y l r。每组查询输出一个整数，表示满足条件的 $k$ 的数量。

样例

输入

3
2 4 1 10
3 5 1 10
6 10 7 20

输出

5
10
7

输入

2
1000000000000000000 1000000000000000000 1 1000000000000000000
7 7 1 6

输出

1
0

样例解释

当 $x=2$、$y=4$ 时，可表示的整数恰好是 $2$ 的倍数，区间 $[1,10]$ 内共有 $5$ 个。当 $x=6$、$y=10$ 时，可表示的整数是 $2$ 的倍数，区间 $[7,20]$ 内共有 $7$ 个。

思路分析

第一步：刻画哪些整数可以被表示

设 $g=\gcd(x,y)$。由于 $g$ 同时整除 $x$ 和 $y$，任意整数线性组合 $a\cdot x+b\cdot y$ 都是 $g$ 的倍数。

根据裴蜀定理，存在整数 $p$、$q$ 使得

等式两边乘以任意整数 $m$，就能表示 $m\cdot g$。因此，可表示的整数集合恰好是 $g$ 的所有整数倍。

第二步：统计区间内的倍数

不超过 $z$ 的正整数中，$g$ 的倍数有 $\lfloor z/g\rfloor$ 个。因此闭区间 $[l,r]$ 内的倍数数量为

使用 $l-1$ 是为了在 $l$ 本身为 $g$ 的倍数时正确包含左端点。

正确性说明

裴蜀定理说明一个整数能表示为 $x$ 和 $y$ 的整数线性组合，当且仅当它是 $\gcd(x,y)$ 的倍数。前缀计数 $\lfloor z/g\rfloor$ 精确统计 $[1,z]$ 内的倍数个数，用两个前缀相减后，得到的正是 $[l,r]$ 内可表示整数的数量。

题解代码

import sys
from math import gcd

input = sys.stdin.readline


def solve():
    t = int(input())
    answers = []

    for _ in range(t):
        x, y, left, right = map(int, input().split())
        divisor = gcd(x, y)
        count = right // divisor - (left - 1) // divisor
        answers.append(str(count))

    print("\n".join(answers))


solve()

复杂度分析

时间复杂度：每组查询为 $O(\log(\min(x,y)))$，开销来自欧几里得算法求最大公约数。

空间复杂度：$O(1)$，除输出数组外只使用常数个变量。

易错点

• $a$、$b$ 是任意整数，不要求非负；若限制为非负整数，就不能直接套用裴蜀定理计数
• 闭区间前缀相减应使用 (left - 1) // divisor
• 数值可能达到 $10^{18}$，其他语言实现时要使用 64 位整数

小结

• 第一题通过阶乘增长性质把大范围问题压缩成常数规模预处理，并用整数平方根规避精度问题
• 第二题用裴蜀定理把线性组合问题转化为最大公约数的倍数计数
• 两题都体现了数论笔试题的常见思路：先刻画可行集合，再做高效计数

资料来源

• AK的互联网offer工坊：蔚来2026-7-26笔试题解