来自 2026 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2026)决赛。
题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。
欣赏完绚丽的幻光留影,大家又被不远处的积木消除小游戏区吸引了目光。
桌面上整齐排列着五颜六色的积木。小 T 和小 S 作为摊主,各自提供了一个能够批量消除积木的魔法筛网。游戏规则很简单:大家可以反复使用这两个筛网进行消除,最终根据桌面上剩余总积木数量进行排名。
桌面上整齐排列着 堆积木,第 堆的初始数量为 。
小 T 和小 S 分别提供了网眼大小为 的两个魔法筛网,能将覆盖的积木堆按对应的模数取余,从而将积木批量消除。在自然展开时,这两个筛网都恰好跨越 堆积木的宽度。它们具有特殊的弹性,可以向两端自由拉伸以覆盖更长的范围,但无法向内压缩收拢。魔法筛网的使用方式如下:
- 选定一段长度至少为 的连续的积木区间 并铺上筛网;
- 从两个魔法筛网中任选一个,即选定 ;
- 对于区间 内的每一堆积木,将其数量对 取余,即令 。
既然参与了这场游戏,你自然不满足于平庸的成绩。为了在排行榜上拔得头筹,你想知道,通过反复使用任意次数的魔法筛网,最终桌面上剩余的积木总数(即 )最少能被消除到多少?