目录题目思路Code题目题目内容所有大于 1 的整数都可以唯一分解为质数的乘积这些质数称为该整数的质因子。例如12 2 × 2 × 312 的质因子为 2 和 37 的质因子为 7。现给定一个正整数 n 和一个严格递增的质数列表 nums请统计 1 到 n 中有多少个正整数的质因子只出现在 nums 中。数字 1 没有质因子也作为符合条件的数字计入答案。1 ≤ n ≤ 10^121 ≤ nums 的长度 m ≤ 5。输入描述第一行输入正整数 n。第二行输入质数列表长度 m。第三行输入 m 个以英文逗号分隔、严格递增的质数。输出描述输出一个整数表示 1 到 n 中质因子只来自 nums 的正整数数量。样例 1输入10 2 2,3输出7说明符合条件的数字为 1、2、3、4、6、8、9共 7 个。样例 2输入15 3 2,3,5输出11说明符合条件的数字为 1、2、3、4、5、6、8、9、10、12、15共 11 个。思路整体思路质因子只来自 nums 的数字一定能唯一写成 p1^e1 × p2^e2 × ... × pm^em其中每个指数都是非负整数。按质数顺序枚举每个指数就能直接统计所有不超过 n 的合法乘积。第一步从乘积 1 和质数下标 0 开始递归。初始乘积 1 对应所有指数都为 0因此数字 1 会自然计入不需要单独补算。第二步在当前递归层固定一个质数让它的指数依次取 0、1、2 等所有仍使乘积不超过 n 的值。每确定一个指数就递归处理下一个质数。第三步当所有质数都已处理时当前指数向量唯一对应一个合法数字答案加 1。质因数分解的唯一性保证不同指数向量不会生成同一个数字因此无需集合去重。第四步继续乘当前质数前先判断当前乘积是否大于 n 除以该质数。如果成立下一次乘法必定超出上限立即停止当前层枚举同时避免整数乘法溢出。正确性说明任意合法数字都能唯一表示为 nums 中各质数的非负整数次幂乘积递归会枚举到它对应的唯一指数向量递归生成的每个乘积又只使用 nums 中的质数且不超过 n所以不会计入非法数字。算法既不遗漏也不重复。边界处理n 为 1 时只统计数字 1质数个数最少为 1 时递归逻辑不变n 达到 10^12 时使用 64 位整数并在乘法前通过除法判断上界。复杂度分析设符合条件的数字数量为 K、质数个数为 m时间复杂度为 O(Km)递归栈空间复杂度为 O(m)。m 最大为 5。Codeimport java.util.Scanner; public class Main { private static long countProducts(int index, long current, long limit, long[] primes) { // 前 index 个质数的指数已经确定到达末尾时current 唯一对应一个合法数字。 if (index primes.length) { return 1; } long total 0; long value current; long prime primes[index]; // value 依次包含当前质数的 0 次、1 次、2 次幂每个选择再递归组合后续质数。 while (value limit) { total countProducts(index 1, value, limit, primes); // 乘法前用除法判断上界避免 value * prime 超过 n 或溢出 long。 if (value limit / prime) { break; } value * prime; } return total; } public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 逗号与空白都作为分隔符可直接读取第三行的英文逗号数组。 scanner.useDelimiter([\\s,]); long n scanner.nextLong(); int m scanner.nextInt(); long[] primes new long[m]; for (int i 0; i m; i) { primes[i] scanner.nextLong(); } // 从乘积 1 出发指数全为 0 的分支会把数字 1 计入答案。 System.out.println(countProducts(0, 1L, n, primes)); } }Gopackage main import ( fmt io os strconv strings unicode ) func countProducts(index int, current int64, limit int64, primes []int64) int64 { // 前 index 个质数的指数已经确定全部处理完时current 唯一对应一个合法数字。 if index len(primes) { return 1 } var total int64 value : current prime : primes[index] // value 依次表示当前质数取 0、1、2... 次幂后的乘积每个选择再组合后续质数。 for value limit { total countProducts(index1, value, limit, primes) // 乘法前用除法判断下一项是否超过 n避免无效分支和 int64 溢出。 if value limit/prime { break } value * prime } return total } func main() { data, _ : io.ReadAll(os.Stdin) // 来源一用三行逗号格式同时按逗号和空白切分即可得到连续的参数序列。 fields : strings.FieldsFunc(string(data), func(r rune) bool { return r , || unicode.IsSpace(r) }) n, _ : strconv.ParseInt(fields[0], 10, 64) m, _ : strconv.Atoi(fields[1]) primes : make([]int64, m) for i : 0; i m; i { primes[i], _ strconv.ParseInt(fields[i2], 10, 64) } // 初始乘积 1 对应所有质数指数均为 0因此数字 1 已包含在答案中。 fmt.Println(countProducts(0, 1, n, primes)) }C#include stdio.h long long count_products( int index, long long current, long long limit, const long long primes[], int size ) { // 前 index 个质数的指数已经确定全部处理完时current 唯一对应一个合法数字并累计到答案。 if (index size) { return 1; } long long total 0; long long value current; long long prime primes[index]; // 循环枚举当前质数的 0 次、1 次、2 次幂每种选择再组合后面的质数。 while (value limit) { total count_products(index 1, value, limit, primes, size); // 先除后比较可判断下一次乘法必定越界同时避免有符号整数乘法溢出。 if (value limit / prime) { break; } value * prime; } return total; } int main(void) { long long n; int m; // 先读取上限 n 和质数个数 m再从第三行解析对应数量的质数。 scanf(%lld%d, n, m); long long primes[5]; for (int i 0; i m; i) { scanf(%lld, primes[i]); // 来源一的第三行用英文逗号分隔最后一个质数后没有逗号需要消费。 if (i 1 m) { scanf( ,); } } // 从乘积 1 出发指数全为 0 的分支自然代表数字 1。 printf(%lld\n, count_products(0, 1, n, primes, m)); return 0; }【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。