贝壳找房 · 数论 · 算法编程题
贝壳找房 数论 时限 1 秒 / 256 MB

题目描述

我们定义任意一个序列的最大公约数为最大的能整除序列中所有数的数
例如序列 \2, 2, 4 的最大公约数为 2 ， \1, 2, 4 的最大公约数为 1
现在牛牛想知道，对于一个长度为 N 的序列，如果他至多能删除 N - 1 个数，请问他最少需要删除多少个数才能让序列的最大公约数变为 1 ，或者这根本是不可能的

输入输出

输入描述
第一行输入一个整数 T ，表示数据组数
对于每组数据，
第一行输入一个整数 N
接下来一行 N 个整数表示序列中的数
输出描述
输出T个整数，若可能，则输出最少需要删除的数，若不可能，则输出-1

样例共 1 组

样例 1 · 对于第一个序列，可以证明，无论删除哪几个数，都无法使序列的gcd变为1 对于第二个序列，不需要删除
输入
2
3
2 2 4
2
1 2
输出
-1
0

算法解析依据一般

考点：数论

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：数论

围绕整除、质因数、同余的经典结论与筛法。

思路框架（数论 通法 · 非本题专属）

  1. 先做质因数分解（试除到 √n，或预处理筛出 1e6 内质数）。
  2. 按题意套结论：约数个数 = Π(e_i+1)；gcd / lcm 用辗转相除法。
  3. 涉及大数取模时，每一步运算后都取模，避免溢出。
  4. 需要区间内质数时用埃氏筛 / 线性筛。

实现要点：模运算规律：(a+b)%m = ((a%m)+(b%m))%m，乘法则同理；减法要 +m 防止负数。

复杂度：时间 O(√n) 分解 / O(n log log n) 筛 ｜ 空间 O(n) 筛表

该范式的通法易错点

  • 取模后相减为负数没处理。
  • a*b 在取模前就溢出了。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 2 / 3 / 2 2 4 / 2 / 1 2 → 输出 -1 / 0

对于第一个序列，可以证明，无论删除哪几个数，都无法使序列的gcd变为1

对于第二个序列，不需要删除

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：贝壳找房2023届校招算法卷1。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解