1000ms

Difficulty: 4

所属公司 : 饿了么

时间 :2025年3月7日(算法方向)

算法与标签>思维

会员或题库专享

请先，开通会员或购买题库饿了么机考编程题库，可解锁完整内容。

购买饿了么机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（饿了么机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

单点贡献：只取一块矿石 $a_i$ 时， $f = g = a_i$ ，乘积为 $a_i^2$ 。因此答案至少是数组最大值的平方。
多元素不会更优：连续多块时， $g(b)$ 不会超过段内最小值，更不会超过全局最大值； $f(b)$ 作为异或和也难以同时把两项都抬到超过最大值平方的程度。直观上，最优值就是最大能量值的平方。
实现：对每组数据扫描一遍序列，记下最大值 $M$ ，输出 $M^2$ 。注意用 $64$ 位整数防止平方溢出。
零值：若出现 $0$ ，由于 $\gcd(0,x)=x$ ，单点 $0$ 的贡献为 $0$ ，不会超过正的最大值平方。

复杂度分析

题目内容

一条矿道上依次埋着 $n$ 块矿石，第 $i$ 块的能量值为 $a_i$ 。对于一段连续矿段 $b$ （即原序列的一个非空连续子数组），定义：

$f(b)$ 为该段所有能量值的按位异或和；
$g(b)$ 为该段所有能量值的最大公约数。

约定 $\gcd(0, x) = x$ （对任意 $x$ 成立）。请选出一段连续矿段，使得 $f(b) \times g(b)$ 最大，并输出这个最大值。