摘要
Title: ARC084_b Small Multiple
Tag: 双端队列广搜、最短路、取模
Memory Limit: 64 MB
Time Limit: 1000 ms

ARC084_b Small Multiple

题意

Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K.
给出一个正整数 K(K∈[2,10^5])，求一个正整数 X使得 X≡0modK且 X的各个位的数字之和最小（比如 123的各个位的数字之和为 1+2+3=6）,输出 X各个位的数字之和。
思路

求一个数的倍数中，哪个数的各个位数字之和最小，最小为多少

双端队列广搜
从1开始搜起并连边，这样可以把所有数都搜出来，直到这个数%k=0
- 首先可以在模k意义下连边：
  - i到 i+1连一条长度为 1的边（各个位数字之和 +1）
  - i到 i×10连一条长度为 0的边（各个位置数字之和不变）
    （注意 i+1和 i×10都是要对k取模的）
为什么要取模k
因为我们只关心取模k后的值是否为0，是否进行取模运算与结果无关
比如 $[(x + 1) \% k * 10] \% k = [(x + 1) * 10] \% k$

这样问题就转化为了边长只有0，1的最短路问题，即双端队列广搜

取模运算规则

代码

'''
Author: NEFU AB-IN
Date: 2022-02-27 19:10:12
FilePath: \ACM\AtCoder\arc084b.py
LastEditTime: 2022-02-27 19:35:39
'''

from collections import deque

N = int(1e6 + 10)
INF = int(2e9)
dist, st = [INF] * N, [0] * N
q = deque()


def bfs(n):
    q.append(1)
    dist[1] = 1

    while q:
        t = q.popleft()
        if st[t]:
            continue
        st[t] = 1
        if t % n == 0:
            return dist[0]
        if dist[(t + 1) % n] > dist[t] + 1:
            dist[(t + 1) % n] = dist[t] + 1
            q.append((t + 1) % n)
        if dist[(t * 10) % n] > dist[t]:
            dist[(t * 10) % n] = dist[t]
            q.appendleft((t * 10) % n)


if __name__ == "__main__":
    n = int(input())
    print(bfs(n))

ARC084_b Small Multiple

题意

思路

代码