多源 Bar 同步周期:bar 长度数组的 LCM 取模
Multi-Feed Bar-Sync Period: LCM Modulo p
开始编码实现 solution(bar_periods: list[int], p: int) -> int。一个对账系统跑着 K 路独立数据源,每路 bar 收盘的周期不同(例如 60 表示 1 分钟 bar、300 表示 5 分钟 bar、3600 表示 1 小时 bar)。请返回 bar_periods 中所有值的 最小公倍数,并对 p 取模——这是所有数据源同时收盘 bar 的同步周期,并按下游调度器/哈希桶消费者所需的模数规约后返回。
例
solution([60, 300, 3600], 1000000007) 返回 3600。三路数据源分别每 60s、300s、3600s 收一根 bar,它们每隔 lcm(60, 300, 3600) = 3600 秒同时对齐一次,而 3600 mod 1000000007 = 3600。solution([60, 90], 1000000007) 返回 180(lcm(60, 90) = 180,两路源每 3 分钟重新对齐一次)。solution([7], 5) 返回 2(单元素的 lcm 即该元素本身,7 mod 5 = 2)。
规约必须是迭代的两两 lcm(a, b) = a // gcd(a, b) * b,从左到右折叠,运行值保持为无界 int。中途取 % p 会破坏下一步的 gcd 和整除——模运算不保留整除性——只在最终返回时取一次 % p。
实现细节由 stubs/stub.py 提供。
实践背景
多源分析层需要准确知道所有 K 路上游源何时同时收盘一根 bar,以便跨源信号(联合波动率、对公共参考做的回归残差、多资产风险归因)能在恰当时刻重算且各源都不滞后。这个同步周期正是各源 bar 时长的 LCM。下游消费这一周期的调度器只关心其 mod p 的值——在槽表宽度为 p 的固定宽度哈希桶调度器里,每项任务落在 lcm(bar_periods) mod p 的槽位上。由于无界 LCM 可达几百位、而槽下标是有界的,约定是"精确计算,规约后返回"。中途模规约就是经典的错误捷径:它会丢掉折叠链所依赖的整除结构,最后得到的槽下标与真实同步周期毫无关系。
约束条件
- 1 <= K <= 50,其中 K = len(bar_periods)
- 每个 `bar_periods[i]` 为正整数且 `1 <= bar_periods[i] <= 10000`
- 1 <= p <= 2_000_000_000(正整数模数;不要求为素数)
- 输出为 `lcm(bar_periods) mod p`,是位于 `[0, p)` 内的非负整数,使用精确比对
- 中间的 LCM 以无界 `int`(Python bigint)保存,仅在末尾对 `p` 取模;中途取模会破坏基于 gcd 的折叠链
样例
Case 1 · statement-example: lcm(60,300,3600) mod 1e9+7 = 3600
输入: [[60,300,3600],1000000007]
期望: 3600
lcm(60, 300, 3600) = 3600;3600 mod 1000000007 = 3600。
Case 2 · visible: two-feed lcm(60, 90) mod 1e9+7 = 180
输入: [[60,90],1000000007]
期望: 180
lcm(60, 90) = 180;180 mod 1000000007 = 180。
Case 3 · visible: single feed reduced mod small p
输入: [[7],5]
期望: 2
单元素 lcm 即该元素本身;7 mod 5 = 2。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: lcm(60,300,3600) mod 1e9+7 = 3600
输入: [[60,300,3600],1000000007]
期望: 3600
lcm(60, 300, 3600) = 3600;3600 mod 1000000007 = 3600。
Case 2 · visible: two-feed lcm(60, 90) mod 1e9+7 = 180
输入: [[60,90],1000000007]
期望: 180
lcm(60, 90) = 180;180 mod 1000000007 = 180。
Case 3 · visible: single feed reduced mod small p
输入: [[7],5]
期望: 2
单元素 lcm 即该元素本身;7 mod 5 = 2。