OPPO · 数论 · 算法编程题
OPPO 数论 n ≤ 1e5 时限 1 秒 / 256 MB

题目描述

小欧有一个长度为 n 的数组，他需要把这个数组分割成 k(k > 1) 1)" /> 个非空子数组，也就是 [l_1, r_1], [l_2, r_2], ·s, [l_k, r_k] ，其中 1 ≤ l_1 < r_1 ≤ l_2 < r_2 ≤ ·s ≤ l_k < r_k ≤ n ，并且 r_i + 1 = l_i + 1 。
对于每个子数组，小欧都会计算出这个子数组的总和 b_i = a_l_i + ... + a_r_i 。
现在小欧想找一个分割方案（子数组数量 k 必须大于 1），使得 gcd(b_1, ..., b_k) 最大，请你帮他找到最大值。
gcd：指最大公约数，Greatest Common Divisor的缩写。

输入输出

输入描述
一行一个整数 n ，表示数组长度。
一行 n 个整数 a_1, ..., a_n ，表示数组的元素。
2 ≤ n ≤ 10^5
1 ≤ a_i ≤ 10^4
输出描述
一个整数，表示最大的 gcd(b_1, ..., b_k) 。

样例共 1 组

样例 1 · 分割成 [1, 2, 3, 4] 和 [5] ，得到 b = [10, 5] ， gcd(10, 5) = 5 ，是最大值。
输入
5
1 2 3 4 5
输出
5

算法解析依据一般

考点：数论

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e5
  • 元素值域：a_i ≤ 1e4（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：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 在取模前就溢出了。

对照本题

  • 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

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

分割成 [1, 2, 3, 4] 和 [5] ，得到 b = [10, 5] ， gcd(10, 5) = 5 ，是最大值。

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

本题来源：2024年秋招-OPPO-前端岗笔试。

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