1. 问题背景与核心概念解析
这个题目来自即将举行的CCPC 2025哈尔滨站程序设计竞赛,属于数论与组合数学交叉领域的难题。题目定义了一个基于无限多重集的函数f(k),要求我们找出这个函数可能达到的最大值以及对应的最小k值。
理解这个问题的关键在于几个核心概念:
-
无限多重集S:集合中包含n种不同的元素{a₁,a₂,...,aₙ},每种元素都有无限多个副本。这意味着我们可以任意选择每个元素的出现次数,只要总数量满足k个即可。
-
k-子集S':从S中选取恰好k个元素(考虑重复)组成子集。例如对于a=[3,6],k=2时可能的子集有{3,3}、{3,6}、{6,6}。
-
子集和的最大公约数f(k):计算所有可能的k-子集元素和,然后求这些和的最大公约数。比如上面的例子中,和分别为6、9、12,它们的gcd是3。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 问题转化与数学建模
2.1 问题重述
我们需要解决的问题可以重新表述为:对于给定的多重集S,定义函数f(k)为所有k-子集和的gcd,找出f(k)的最大值以及使f(k)达到该最大值的最小k。如果f(k)可以无限增大,则输出"infinite"。
2.2 关键观察
通过分析题目描述和样例,我们可以得出几个重要观察:
-
f(k)的表达式:实际上,f(k)可以表示为gcd(a₁,a₂,...,aₙ)×k的某个函数。在第一个样例中,gcd(3,6)=3,且f(k)恒等于3;第二个样例中,gcd=2,f(k)=2k。
-
无限增长的条件:当所有a_i的gcd为d,且a_i/d不全相等时,f(k)=d×k会随着k无限增长。
-
存在最大值的情况:当所有a_i/d相等时,f(k)恒等于d,此时最大值为d,最小k为1。
3. 算法设计与实现
3.1 解题思路
基于上述观察,我们可以设计以下解题步骤:
- 计算所有a_i的最大公约数d = gcd(a₁,a₂,...,aₙ)
- 检查所有a_i/d是否相同:
- 如果相同,则f(k)恒为d,最大值为d,最小k为1
- 如果不全相同,则f(k)=d×k会无限增长,输出"infinite"
3.2 算法实现细节
cpp复制#include <bits/s
