← 返回编程题库
coding-bar-period-lcm-mod中等免费版2000ms未尝试

多源 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 = 3600solution([60, 90], 1000000007) 返回 180lcm(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 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

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。