区间 gcd 与总和的和最大值问题，这个问题有点不会，望高人赐教，谢谢【重金悬赏】
本帖最后由 zhangjinxuan 于 2023-6-6 11:45 编辑【重金悬赏】是吸引你点进来的，但是真的有重金悬赏。
这个题想了亿天了，决定来问亿问。
题目描述
给定一个长度为 n 的正整数序列 a，请找到两个数 l, r，使 gcd(al, al+1, ..., ar) + al, al+1, ..., ar 最大，输出 l, r，并且输出这个最大值。
gcd 表示最大公因数。
例如：
4
9 8 16 24
输出：
2 4
56
解释：gcd(8, 16, 24) + 8 + 16 + 24 = 56，这是最大的。
数据范围：
1 <= n <= 1000000
a 的所有元素都大于等于 1，小于等于 1000000。
想了很久也没有什么头绪，望高人赐教。
@陈尚涵 @额外减小 @tommyyu
成功解决者，额外赏 30 鱼币。 不会，也不敢问 gpt 一个区间可以包含整个吗？ liuzhengyuan 发表于 2023-6-5 19:12
一个区间可以包含整个吗？
可以 最近高考啊，现在冷清啊。 不会 {:10_250:}
from collections import defaultdict
def factor_sieve(n):
"""
返回一个list，表示小于等于n的所有数的最小质因子
"""
sieve = * (n + 1)
for i in range(2, n + 1):
if sieve == 0:# i是质数
for j in range(i * i, n + 1, i):
if sieve == 0:
sieve = i
return sieve
def get_factor_counts(sieve, x):
"""
返回x的所有质因子的出现次数的和，如20=2*2*5，返回4+1=5
"""
counts = defaultdict(int)
while x > 1:
prime = sieve
if prime == 0:
prime = x
counts += 1
x //= prime
return sum(counts.values())
n = int(input())
a = list(map(int, input().split()))
sieve = factor_sieve(max(a))
# 预处理每个数在各个质因子下的出现次数，放到二维数组counts中
counts = [ * len(sieve) for _ in range(n)]
for i in range(n):
for j in range(len(sieve)):
if a % (j+1) == 0:
counts = get_factor_counts(sieve, a // (j+1))
# 计算每个左端点和右端点的区间公因数及其总和，找到最大值
best_l, best_r, best_value = -1, -1, 0
for l in range(n):
prod_counts = * len(sieve)
for r in range(l, n):
for j in range(len(sieve)):
prod_counts += counts
# 计算当前区间的公因数及其总和
factor = 1
sum_of_divisors = 0
for j in range(len(sieve)):
if prod_counts == r - l + 1:
factor *= (j+1)
sum_of_divisors += prod_counts * (j+1)
value = factor + sum_of_divisors
# 更新最大值
if value > best_value:
best_l, best_r, best_value = l, r, value
print(best_l+1, best_r+1)
print(best_value) sfqxx 发表于 2023-6-5 22:15
强 额外减小 发表于 2023-6-6 00:10
强
不是我做的 sfqxx 发表于 2023-6-5 22:15
时间复杂度怎么算{:10_277:} 本帖最后由 zhangjinxuan 于 2023-6-6 07:56 编辑
sfqxx 发表于 2023-6-5 22:15
37 行，j 应该是第几个质数，所以不应该是 a[ i] % sieve == 0 吗？
还有，你这样的时间复杂度是 n^2 啊，n^2 的算法很简单的。
我问 chatgpt 5 遍都是 n^2 算法{:10_250:} 本帖最后由 zhangjinxuan 于 2023-6-6 07:56 编辑
额外减小 发表于 2023-6-6 00:10
强
他时间复杂度 n^2{:10_250:} a是正整数序列，最大的连续区间怎么理解？ 使这个区间的公因数与总和的和的值最大
//使区间公因数的值最大。总和的值最大。
这题表达有问题（个人观点） zhenjen 发表于 2023-6-6 10:47
使这个区间的公因数与总和的和的值最大
//使区间公因数的值最大。总和的值最大。
这题表达有问题（个人观 ...
使这个区间的 最大公因数 与 数字总和 的和的值最大 zhenjen 发表于 2023-6-6 10:47
使这个区间的公因数与总和的和的值最大
//使区间公因数的值最大。总和的值最大。
这题表达有问题（个人观 ...
行吧，还是用形式化的语言来说（ zhangjinxuan 发表于 2023-6-6 11:08
使这个区间的 最大公因数 与 数字总和 的和的值最大
问下，输出的2 4是什么意思？ zhenjen 发表于 2023-6-6 11:14
问下，输出的2 4是什么意思？
就是 l, r 个人思路：1.找包含公因数的区间。h=gcd（）+包含公因数区间k，记录左右端点。n=h。2.加if（h＞n）更新记录点。3.重复
继续找包含公因数的区间与 zhenjen 发表于 2023-6-6 11:27
个人思路：1.找包含公因数的区间。h=gcd（）+包含公因数区间k，记录左右端点。n=h。2.加if（h＞n）更新记录 ...
给定一个正整数序列 a，请找到两个数 l, r，使 gcd(al, al+1, ..., ar) + al, al+1, ..., ar 最大，输出 l, r，并且输出这个最大值。
gcd 表示最大公因数。