T30868:upstairs

同余最短路, http://cs101.openjudge.cn/practice/30868

有一层楼一共有 n 层，小 z 从第 0 层出发，想要前往某一层。上楼的方式只有一个奇怪的电梯，这个电梯每次只能向上走 a 层，b 层，或 c 层。小 z 想知道，对于某一个楼层，他能否通过这个电梯到达。由于小 z 想去的楼层数比较多，他会给你多组询问。每次小 z 都会回到第 0 层重新出发。

形式化地，对于给定的 a,b,c，是否存在自然数解 (x,y,z)，使得对于某个询问 hi，满足 hi=ax+by+cz。

数据范围：

对于全部数据，0 ≤ hi ≤ n, 0 ≤ q ≤ 10^5, 1 ≤ n ≤ 10^{18}, 0 ≤ a,b,c ≤ 10^6。

对于 1% 的数据，为样例。

对于另外 9% 的数据，a=0, 0 ≤ b,c ≤ 10^3, 1 ≤ q ≤ 10^3,1 ≤ n ≤ 10^5。

对于 30% 的数据，0 ≤ a,b,c ≤ 10^3, 1 ≤ q ≤ 10^3, 1 ≤ n ≤ 10^9。

对于 50% 的数据，0 ≤ a,b,c ≤ 3 * 10^3，且 b,c 互质。

对于 70% 的数据，0 ≤ a ≤ 10^4。

输入

一共 q+2 行。第一行有 3 个数，分别代表 a,b,c。第二行有 1 个数 q，表示接下来有 q 组询问。对第 3 行至第 q+2 行，每行一个数 hi(1 ≤ i ≤ q)，表示小 z 想要前往的楼层数。

输出

一共 q 行，每行一个字符串。如果小 z 能够到达，输出 Yes，否则输出 No。

样例输入

sample1 input:
7 3 5
4
4
10
13
41

sample1 output:
No
Yes
Yes
Yes

解释：可以证明，第 4 层无法到达，而 10 = 5+5,13 = 7+3+3，41 = 7+7+7+7+7+3+3。
到达该层的方案不唯一。

样例输出

sample2 input:
13 53 39
5
414
690
597
390
144

sample2 output:
No
Yes
No
Yes
Yes

提示：同余最短路

来源：2026 spring ZHUJingqi

思路：同余最短路。选择a,b,c中最小的数（不妨a）作为最后叠加的层数，问题转化为在模a意义下，h=by+cz，而当此时的h最小，它是否小于目标的h。因此对每个余数u构建(u+b) mod a和(u+c) mod a的路径，从0开始跑一遍Dijkstra，得到的即为最小的h.

python

import heapq
a,b,c=map(int,input().split())
query=int(input())
step=[]
if(a>0):
    step.append(a)
if(b>0):
    step.append(b)
if(c>0):
    step.append(c)
step.sort()
if(len(step)>=2):
    m=step[0]
    edges=step[1:]
    dist=[float("inf")]*m
    dist[0]=0
    q=[]
    heapq.heappush(q,(0,0))
    while(q):
        d,node=heapq.heappop(q)
        if(d>dist[node]):
            continue
        for i in edges:
            nxt=(node+i)%m
            if(dist[nxt]>d+i):
                dist[nxt]=d+i
                heapq.heappush(q,(dist[nxt],nxt))
def solve(h):
    if(len(step)==0):
        if(h==0):
            return True
        else:
            return False
    elif(len(step)==1):
        if(h%step[0]==0):
            return True
        else:
            return False
    rem=h%m
    if(dist[rem]<=h):
        return True
    else:
        return False
for i in range(query):
    h=int(input())
    if(solve(h)):
        print("Yes")
    else:
        print("No")

这道题是一道典型的同余最短路问题。

1. 为什么使用同余最短路？

要判断是否存在非负整数解 $(x, y, z)$ 满足 $a x + b y + c z = h_{i}$ 。由于 $h_{i}$ 的范围高达 $10^{18}$ ，直接进行完全背包或暴力搜索显然会超时。同余最短路的基本思想是：

选择一个非零步长（例如最小的步长 $m$ ）作为模数。
对于任意一个可以到达的楼层 $H$ ，它必然可以表示为 $H = k \cdot m + R$ ，其中 $R = H (\mod m)$ 且 $k$ 是非负整数。
只要我们能用其余的步长（ $b, c$ ）组合出某个值 $V$ ，使得 $V \equiv R (\mod m)$ ，那么所有大于等于 $V$ 且模 $m$ 同余 $R$ 的楼层 $H$ 都可以通过不断累加步长 $m$ 来到达。
因此，我们的目标是求出在模 $m$ 意义下，能够到达的最小数值。这个最小值就是源点 $0$ 到余数状态的最短距离。

2. 建图与状态转移

状态（节点）：模 $m$ 的余数，共 $m$ 个状态（ $0, 1, \dots, m - 1$ ）。
边（转移）：对于状态 $u$ ，可以通过加上其他步长 $v$ （例如 $b$ 或 $c$ ）转移到新状态 $(u + v) (\mod m)$ ，边权为 $v$ 。
算法：从起点 $0$ 出发，使用 Dijkstra 算法求出单源最短路，记 $d i s t [r]$ 为到达模 $m$ 余数为 $r$ 的最小楼层数。
查询判断：对于询问 $h_{i}$ ，令 $r = h_{i} (\mod m)$ 。若 $d i s t [r] \leq h_{i}$ ，说明能到达，输出 Yes；否则输出 No。

3. 复杂度分析

时间复杂度：若选择最小的非零步长 $m \leq 10^{6}$ ，图的点数为 $m$ ，边数最多为 $2 m$ 。使用堆优化的 Dijkstra 算法，时间复杂度为 $O (m \log m)$ 。每次查询的时间复杂度为 $O (1)$ 。总时间复杂度为 $O (m \log m + q)$ ，在 Python 中需要进行一定的常数优化以避免超时。
空间复杂度：需要存储距离数组 dist 和优先队列，空间复杂度为 $O (m)$ 。

代码优化点

快速 I/O（输入输出优化）：由于询问次数 $q \leq 10^{5}$ ，逐行读取和打印在 Python 中开销很大。我们使用 sys.stdin.read 一次性读取所有输入，并用 sys.stdout.write 或 '\n'.join() 批量输出。
边界条件处理：
- 若所有步长均为 $0$ ，则只能到达 $0$ 层。
- 若只有一个非零步长，则只需判断目标楼层是否是该步长的倍数。
- 排除为 $0$ 的步长，避免建图时产生自环或模数为 $0$ 的错误。

python

import sys
import heapq

def solve():
    # 使用 sys.stdin.read 一次性读取所有输入，提升 I/O 效率
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 解析输入
    a = int(input_data[0])
    b = int(input_data[1])
    c = int(input_data[2])
    q = int(input_data[3])
    queries = [int(x) for x in input_data[4 : 4 + q]]
    
    # 过滤掉为 0 的步长，并从小到大排序
    steps = sorted([x for x in (a, b, c) if x > 0])
    
    # 特殊情况 1：没有可行的步长
    if not steps:
        results = ["Yes" if h == 0 else "No" for h in queries]
        sys.stdout.write('\n'.join(results) + '\n')
        return
        
    # 特殊情况 2：只有一种步长
    if len(steps) == 1:
        step = steps[0]
        results = ["Yes" if h % step == 0 else "No" for h in queries]
        sys.stdout.write('\n'.join(results) + '\n')
        return

    # 同余最短路：选择最小的非零步长作为模数 m
    m = steps[0]
    edges = steps[1:] # 剩余的步长作为转移边
    
    # dist[r] 表示模 m 余数为 r 时，能到达的最小楼层高度
    dist = [float('inf')] * m
    dist[0] = 0
    
    # 优先队列 (距离, 节点)
    pq = [(0, 0)]
    
    # 堆优化 Dijkstra 过程
    while pq:
        d, u = heapq.heappop(pq)
        
        # 剪枝：如果当前取出的距离大于已知最短距离，则跳过
        if d > dist[u]:
            continue
            
        # 尝试通过其余的步长进行转移
        for step in edges:
            nxt = (u + step) % m
            nd = d + step
            if dist[nxt] > nd:
                dist[nxt] = nd
                heapq.heappush(pq, (nd, nxt))
    
    # 处理每组询问
    results = []
    for h in queries:
        rem = h % m
        # 如果要到达的目标高度 h 大于等于模 m 同余下的最小可达高度，则可行
        if dist[rem] <= h:
            results.append("Yes")
        else:
            results.append("No")
            
    # 批量输出结果
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

T30868:upstairs ​

T30868:upstairs