通用最小价位单元:跨场所 tick size 的最大公约数
Universal Tick Unit: GCD of Per-Venue Tick Sizes
开始编码实现 solution(tick_sizes: list[int]) -> int。一段行情归一化逻辑接收 N 个场所对同一标的报价时使用的整型 tick size 列表(单位为某种次美分子单元)。请返回所有 tick 的最大公约数——能整除每个场所 tick 的最小价位单元,亦即所有挂单簿统一对齐到的"通用次价位"。
例
solution([6, 9, 15]) 返回 3。各场所分别按 6、9、15 个次价位单元报价,但每个 tick 都是 3 的倍数,因此 3 是通用次价位。solution([4, 9]) 返回 1(两数互质,没有比 1 更细的公共 tick)。solution([7]) 返回 7(仅有一家场所时,其 tick 自身即为通用单元)。
需要明确的细节:空输入返回 0;任意 tick <= 0 抛 ValueError(负数或零均非合法行情)。规约必须使用迭代欧几里得算法(math.gcd),整体复杂度 O(N * log M),其中 M 为最大 tick;从 1 开始枚举候选除数的方案是 O(N * M),在隐藏用例把单个 tick 推到 10^12 量级时会超时。
实现细节由 stubs/stub.py 提供。
实践背景
当多个场所对同一标的按略有不同的价位栅格报价时——例如一家以 1/100 美分为 tick,另一家以 1/250 美分为 tick——希望把所有挂单簿叠到同一"通用栅格"上的归一化层就需要选一个能整除每个场所 tick 的次价位。所有 tick 的最大公约数恰好是这一选择:在仍尊重每家场所离散化的前提下、最粗的公共单位。比 gcd 更细的栅格是浪费分辨率;比 gcd 更粗则至少在一家场所上会丢失可表示的价位。Tick-size 归一化器在 session 开始时对场所列表跑一次该规约,然后把所有进来的报价都桶化到生成的统一栅格上,下游信号消费的 spread、mid、深度统计因此可在跨场所之间相互比较。
约束条件
- 0 <= N <= 200000,其中 N 为 solution(tick_sizes) 的输入长度
- 每个 tick_sizes[i] 为不超过 10^12 的正整数
- 空输入返回 0
- 任意 tick <= 0 抛 ValueError
- 输出为非负整数,使用精确比对
样例
Case 1 · statement-example: gcd(6,9,15)=3
输入: [[6,9,15]]
期望: 3
6=2·3,9=3²,15=3·5 的最大公约数为 3。
Case 2 · visible: coprime pair returns 1
输入: [[4,9]]
期望: 1
4 与 9 互质,最大公约数为 1。
Case 3 · visible: single tick returns itself
输入: [[7]]
期望: 7
单元素集合的 gcd 即为该元素本身。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: gcd(6,9,15)=3
输入: [[6,9,15]]
期望: 3
6=2·3,9=3²,15=3·5 的最大公约数为 3。
Case 2 · visible: coprime pair returns 1
输入: [[4,9]]
期望: 1
4 与 9 互质,最大公约数为 1。
Case 3 · visible: single tick returns itself
输入: [[7]]
期望: 7
单元素集合的 gcd 即为该元素本身。