Problem:
 Score : 700 points    Problem Statement Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K .      Constraints  2 \leq K \leq 10^5  K is an integer.         Input Input is given from Standard Input in the following format:  K       Output Print the smallest possible sum of the digits in the decimal notation of a positive multiple of K .        Sample Input 1 6      Sample Output 1 3  12=6×2 yields the smallest sum.       Sample Input 2 41      Sample Output 2 5  11111=41×271 yields the smallest sum.       Sample Input 3 79992      Sample Output 3 36

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    k = int(input())
    dist = [INF] * k
    dist[1] = 1
    queue = [1]

    for v in queue:
        tmp = [v]
        for v in tmp:
            if dist[10 * v % k] > dist[v]:
                dist[10 * v % k] = dist[v]
                tmp.append(10 * v % k)
            if dist[(v + 1) % k] > dist[v] + 1:
                dist[(v + 1) % k] = dist[v] + 1
                queue.append((v + 1) % k)

    print(dist[0])
resolve()

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    k = int(input())
    dist = [INF] * k
    dist[1] = 1
    queue = deque([1])

    while queue:
        v = queue.pop()
        if dist[10 * v % k] > dist[v]:
            dist[10 * v % k] = dist[v]
            queue.appendleft(10 * v % k)
        if dist[(v + 1) % k] > dist[v] + 1:
            dist[(v + 1) % k] = dist[v] + 1
            queue.append((v + 1) % k)

    print(dist[0])
resolve()

Solution (Python):
import heapq
k = int(input())
graph = [[] for i in range(k)]
for i in range(k):
    if i != k-1: graph[i].append((1, i+1))
    else: graph[i].append((1, 0))
    if (i * 10) % k != i: graph[i].append((0, (i * 10) % k))

que = []
heapq.heappush(que, (0, 1, 1)) 
dist = [1145141919] * k
dist[1] = 0

ans = 1145141919
while len(que) > 0:
    d, v, num = heapq.heappop(que)
    for cost, place in graph[v]:
        if place == 0:
            ans = min(ans, num + 1 if cost else num)
        if d + cost < dist[place]:
            dist[place] = d + cost
            heapq.heappush(que, (d + cost, place, (num + 1 if cost else num)))

print(ans)

Solution (Python):
from collections import deque
K=int(input())


INF=10**9
res=[INF]*(K)
res[1]=1
q=deque()
q.append(1)
while q:
    r=q.popleft()
    if r==0:
        break
    nr=(r+1)%K
    if res[r]<res[nr]:
        res[nr]=res[r]+1
        q.append(nr)
    nr=(10*r)%K
    if res[r]<res[nr]:
        res[nr]=res[r]
        q.appendleft(nr)
print(res[0])

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


K = int(input())
q = deque()
q.append((1, 1))
visited = [False] * K
ans = 0
while True:
    s, x = q.popleft()
    if visited[x]:
        continue
    visited[x] = True
    if x == 0:
        ans = s
        break
    q.appendleft((s, (10 * x) % K))
    q.append((s + 1, (x + 1) % K))
print(ans)

Solution (Python):
from collections import deque
k=int(input())
t=[1]*k
q=deque()
q.append((1,1))

while q:
  p,r=q.popleft()
  if p==0:
    print(r)
    break
  if t[p]:
    t[p]=0
    q.appendleft(((p*10)%k,r))
    q.append(((p+1)%k,r+1))

Solution (Python):

import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

K = int(readline())
edges = [[] for _ in range(K)]
INF = 10 ** 31
dist = [INF]*K
for i in range(K):
    edges[i].append(((i+1)%K,1))
    j = 10*i % K
    if i != j:
        edges[i].append((j,0))

q = deque([1])
dist[1] = 0
while q:
    x = q.popleft()
    for y,c in edges[x]:
        d = dist[x] + c
        if d < dist[y]:
            dist[y] = d
            if c == 1:
                q.append(y)
            else:
                q.appendleft(y)
print(dist[0]+1)

Solution (Python):
k = int(input())

ones = set()
x = 1
while(not x in ones):
    ones.add(x)
    x = (x*10)%k

num = 1
mask = (1<<k) -1
for i in range(1,46):
    next = 0
    for j in ones:
        next |= (num<<j)
    num = (next&mask) | (next>>k)

    if(num%2==1):
        print(i)
        exit()

Solution (Python):

from collections import deque
k = int(input())
d = [k] * k
e = [[(0, i * 10 % k), (1, (i + 1) % k)] for i in range(k)]
dq = deque()
dq.append((1, 1))
while dq:
    c, v = dq.popleft()
    for v2nv, nv in e[v]:
        if v2nv == 0:
            if c < d[nv]:
                d[nv] = c
                dq.appendleft((d[nv], nv))
        else:
            if c + 1 < d[nv]:
                d[nv] = c + 1
                dq.append((d[nv], nv))
print(d[0])

Solution (Python):
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
k=int(input())
edge=[[]for _ in range(k)]
for i in range(1,k):
    edge[i].append(((i*10)%k,0))
    edge[i].append(((i+1)%k,1))
ans=dijkstra(1,k,edge)
print(ans[0]+1)

Solution (Python):
from collections import deque
k = int(input())
d = [-1] * (k * 10)
d[0] = 0
q = deque([0])
ans = 100000000
while q:
    p = q.pop()
    x, r = p // 10, p % 10
    if r < 9:
        t = (x + 1) % k * 10 + r + 1
        if t // 10 == 0:
            ans = min(ans, d[p] + 1)
        elif d[t] == -1:
            q.appendleft(t)
            d[t] = d[p] + 1
    t = (x * 10) % k * 10
    if d[p] != 0 and t // 10 == 0:
        ans = min(ans, d[p])
    elif d[t] == -1:
        q.append(t)
        d[t] = d[p]
print(ans)

Solution (Python):

from collections import deque

INF = 10**9
k = int(input())


G = [((10 * i % k, 0), ((i + 1) % k, 1)) for i in range(k)]
s = 1


dist = [INF] * k
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d + c < dist[w]:
                dist[w] = d + c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[0] + 1)

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    """
    「数字の桁数の和に関する問題としては初見はキツいが割と典型らしい」

    全ての整数は1から出発して次の操作のいずれかを組み合わせて表現できる：
        a. 1を加える（ただし一の位が9の時はこの操作は許さない）
        b. 10倍する
    なぜこのような分解をしたかというと、整数をこのように表現することで
        （各桁の和）=（a.の操作を行った回数）+ 1
    と言い換えることができるから。

    そこで頂点を数字、辺を上の操作に当ててBFSすることを考える。
    このままでは頂点数が無限だが、辺の張られ方はmod Kをとっても同様の構造が出てくる。
    そこで無限グラフをmod Kで圧縮して有限グラフに直した上で頂点1から頂点0に移動するための
    最小コストが答え。

    ここでa.の操作で9->10のような遷移は許さなかったが、求めるのは最小コストであって
    1から10にたどり着くにはa.を10回するよりb.を1回する方がコストが低いので、a.の操作を
    一の位が9の場合に許容したとしても最短経路長は変化しない。
    """
    K = int(input())
    repn = [[] for _ in range(K)]
    for i in range(K):
        repn[i].append(10**6 + (i + 1) % K)
        repn[i].append((i * 10) % K)
    q = deque([])
    cost = [0] * K
    cost[1] = 1
    for val in repn[1]:
        type, toward = val // 10**6, val % 10**6
        
        if type == 0:
            q.appendleft(1 * 10**6 + toward)
        else:
            q.append(10**12 + 1 * 10**6 + toward)

    while q:
        x = q.popleft()
        type, x = x // 10**12, x % 10**12
        pre, now = x // 10**6, x % 10**6
        if cost[now] != 0: continue
        cost[now] = cost[pre] + type
        for val in repn[now]:
            type, toward = val // 10**6, val % 10**6
            if type == 0:
                q.appendleft(now * 10**6 + toward)
            else:
                q.append(10**12 + now * 10**6 + toward)

    print(cost[0])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())

K = I()

Graph = [0]*K
for i in range(K):
    if (i+1) % K != (10*i) % K:
        Graph[i] = [(1,(i+1) % K),(0,(10*i) % K)]  
    else:
        Graph[i] = [(0,(10*i) % K)]



from heapq import heappush,heappop

d = [100]*K
d[1] = 1
q = []
heappush(q,(1,1))
v = [False]*K
while q:
    a,n = heappop(q)
    if v[n]:
        continue
    v[n] = True
    for da,dn in Graph[n]:
        if v[dn]:
            continue
        if a+da < d[dn]:
            d[dn] = a+da
            heappush(q,(a+da,dn))

print(d[0])

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())

K = I()

Graph = [0]*K
for i in range(K):
    if (i+1) % K != (10*i) % K:
        Graph[i] = [((i+1) % K,1),((10*i) % K,0)]  
    else:
        Graph[i] = [((10*i) % K,0)]

from collections import deque

q = deque([1])
d = [100]*K
d[1] = 1

while q:
    n = q.pop()
    if n == 0:
        continue
    else:
        for a,b in Graph[n]:
            if d[a] > d[n]+b:
                d[a] = d[n]+b
                if b == 0:
                    q.append(a)
                else:
                    q.appendleft(a)

print(d[0])

Solution (Python):
import sys
from collections import deque
readline=sys.stdin.readline

def main():
    k=int(readline())
    v=list(range(k))
    inf=float('inf')
    dist=[inf]*k
    visited=[0]*k
    stack=deque([1])
    dist[1]=0
    while stack:
        v=stack.pop()
        if not visited[v]:
            nv0=10*v%k
            nv1=(v+1)%k
            if dist[nv0]>dist[v]:
                dist[nv0]=dist[v]
                stack.append(nv0)
            if dist[nv1]>dist[v]+1:
                dist[nv1]=dist[v]+1
                stack.appendleft(nv1)
            visited[v]=1
    print(dist[0]+1)

if __name__=='__main__':
    main()

Solution (Python):
from collections import deque

k=int(input())
v=list(range(k))
stack=deque([1])
inf=float('inf')
visited=[0]*k
dist=[inf]*k
dist[1]=0
while stack:
  v=stack.pop()
  if not visited[v]:
    nv0=10*v%k
    nv1=(v+1)%k
    if dist[nv0]>dist[v]:
      dist[nv0]=dist[v]
      stack.append(nv0)
    if dist[nv1]>1+dist[v]:
      stack.appendleft(nv1)
      dist[nv1]=dist[v]+1
    visited[v]=1
print(dist[0]+1)

Solution (Python):
from collections import deque

K = int(input())

visited=[False]*K
s=(1,1)

q = deque()
q.append(s)

while True:
  c = q.popleft()
  visited[c[0]] = True

  if c[0] == 0:
    print(c[1])
    exit()

  if not visited[(c[0] * 10) % K] and not visited[(c[0] * 10) % K]:
    q.appendleft(((c[0] * 10) % K, c[1]))

  if not visited[(c[0] + 1) % K] and not visited[(c[0] + 1) % K]:
    q.append(((c[0] + 1) % K, c[1] + 1))

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
graph = [[] for i in range(N)]
for i in range(N):
  graph[i].append((1,(i+1)%N))
for i in range(N):
  graph[i].append((0,(i*10)%N))
  
  
def bfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    for c,v in graph[u]:
      if d[v] <= d[u] + c: continue
      d[v] = d[u] + c
      if c:
        q.append(v)
      else:
        q.appendleft(v)
  return d

d = bfs(graph,1)

print(d[0]+1)

Solution (Python):
import collections
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

K = int(input())


def ans():
    visited = [False] * K

    s = (1, 1)

    q = collections.deque()
    q.append(s)

    while True:
        c = q.popleft()
        visited[c[0]] = True

        if c[0] == 0:
            return c[1]

        if not visited[(c[0] * 10) % K] and not visited[(c[0] * 10) % K]:
            q.appendleft(((c[0] * 10) % K, c[1]))

        if not visited[(c[0] + 1) % K] and not visited[(c[0] + 1) % K]:
            q.append(((c[0] + 1) % K, c[1] + 1))


print(ans())

Solution (Python):
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


k = int(input())

graph = [[] for _ in range(k)]
for i in range(1, k):
    graph[i].append((1, (i + 1) % k))
    graph[i].append((0, 10 * i % k))

dist = dijkstra(graph, k, 1)
ans = dist[0] + 1
print(ans)

Solution (Python):
K = int(input())
import collections
d = [float('inf')]*(K)
d[1] = 1
path = [[] for _ in range(K)]
for i in range(K-1):
    path[i].append((i+1,1))

path[-1].append((0,1))
for i in range(K):
    path[i].append(((i*10)%K,0))
deque = collections.deque([1])
while deque:
    s = deque.popleft()
    for e,cost in path[s]:
        if d[s] + cost < d[e]:
            d[e] = d[s]+cost
            if cost ==0: deque.appendleft(e)
            else: deque.append(e)
print(d[0])

Solution (Python):
from collections import*
q=deque([(1,1)])
k=input()
m={}
while q:
 n,s=q.pop()
 if(n in m)-1:m[n]=s;q+=(n*10%k,s),;q.appendleft((-~n%k,s+1))
print m[0]

Solution (Python):
from collections import*
q=deque([(1,1)])
k=int(input())
m={}
while q:
 n,s=q.pop()
 if(n in m)-1:m[n]=s;q+=(n*10%k,s),;q.appendleft((-~n%k,s+1))
print(m[0])

Solution (Python):

from collections import deque

INF = 10**9
k = int(input())


G = [((10 * i % k, 0), ((i + 1) % k, 1)) for i in range(k)]
s = 1


dist = [INF] * k
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d + c < dist[w]:
                dist[w] = d + c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[0] + 1)

Solution (Python):
from collections import deque
def bfs01(K,adjlist):
    reached=[False]*K
    d=deque()
    d.append((1,0))
    reached[1]=True
    while True:
        cur=d.popleft()
        reached[cur[0]]=True
        if cur[0]==0:
            return cur[1]
        for j,w in adjlist[cur[0]]:
            if w==0:
                if not reached[j]:
                    d.appendleft((j,cur[1]))
            elif w==1:
                if not reached[j]:
                    d.append((j,cur[1]+1))
                
    

K=int(input())
adjlist=[[] for _ in range(K)]
for i in range(K):
    to1=(i+1)%K
    to2=(10*i)%K
    if to1==to2:
        adjlist[i]=[(to2,0)]
    else:
        adjlist[i]=[(to1,1),(to2,0)]
print(bfs01(K,adjlist)+1)

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  k = ni()
  q = deque()
  q.append(1)
  dist = [k]*k
  dist[1] = 1
  while q:
    v = q.popleft()
    if dist[(v + 1) % k] > dist[v] + 1:
      dist[(v + 1) % k] = dist[v] + 1
      q.append((v + 1) % k)
    if dist[v*10%k] > dist[v]:
      dist[v*10%k] = dist[v]
      q.appendleft(v*10%k)
  print(dist[0])
  return

solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')


from collections import deque





def solve():
    K = II()

    q = deque([(1, 1)])
    used = [0 for _ in range(K)]
    while len(q) > 0:
        
        v, cost = q.popleft()
        if v == 0:
            print(cost)
            return

        if used[v]:
            continue
        used[v] = 1

        q.appendleft(((v*10) % K, cost))
        q.append(((v+1) % K, cost+1))



if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
k = int(input())

e = [[] for i in range(k)]
for i in range(k):
    e[i].append(((i+1)%k,1))
    if i*10%k != i:
        e[i].append(((i*10)%k,0))

d = [-1]*k
d[1] = 0
q = deque([])
q.append((1,0))
while q:
    now,dis = q.popleft()

    for nex,cost in e[now]:
        if d[nex] == -1 or d[nex] > dis+cost:
            d[nex] = dis+cost
            if cost == 0:
                q.appendleft((nex,dis))
            else:
                q.append((nex,dis+1))

print(d[0]+1)

Solution (Python):
from collections import deque
q = deque()
ans = {}
K = int(input())
q.append((1,1))
while len(q):
  resid,total = q.popleft()
  if resid in ans:
    continue
  ans[resid] = total
  q.appendleft((resid*10%K,total))
  q.append(((resid+1)%K,total+1))
print(ans[0])

Solution (Python):
import sys
K=int(input())

graph=[[] for _ in range(K)]
for i in range(K):
  graph[i].append(((i+1)%K,1))
  graph[i].append(((10*i)%K,0))


dist=[-1]*K
s,t=1,0
queue=[s]
d=0
while queue:
  new_queue=set()
  
  while queue:
    q=queue.pop()  
    if dist[q]==-1:
      dist[q]=d
      for v,w in graph[q]:
        if w==0:
          queue.append(v)
        else:
          new_queue.add(v)
  
  d+=1
  queue=list(new_queue)
  

print(dist[0]+1)

Solution (Python):
K=int(input())
a=K
while a%2==0:
    a//=2
while a%5==0:
    a//=5
if a==1:
    print(1)
else:
    mod=set([])
    a=1
    while a not in mod:
        mod.add(a)
        a*=10
        a%=K

    mod=list(mod)
    n=len(mod)
    wei=pow(2,K)-1
    check=1
    ans=0
    for j in range(0,n):
        ans=ans|(check<<mod[j])
    check=ans
    for i in range(1,46):
        if check>>0 &1==1:
            print(i)
            exit()
        ans=check
        for j in range(0,n):
            ans=ans|(check<<mod[j])
        ans1=ans&wei
        ans2=ans>>K
        check=ans1|ans2

Solution (Python):


import io
import math
import scipy.sparse
import numpy
from collections import deque

q = deque();K=int(input());q+=[(1,1)];m={}

while len(q):
	n,s=q.pop()
	if not n in m:m[n]=s;q+=[(n*10%K,s)];q.appendleft(((n+1)%K,s+1))

print(m[0])

Solution (Python):
import sys




from collections import deque


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[10**5+1]*K
visit=[]
vals[1]=0
q = deque([1])
flag=False
while len(q)>0:
    s=q.popleft()
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.appendleft(s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

K = int(input())

D = [-1]*K

q = deque()
q.append(1)
D[1] = 1
while q:
    p = q.pop()
    n1 = (p*10)%K
    if D[n1] == -1 or D[n1] > D[p]:
        D[n1] = D[p]
        q.append(n1)
    n2 = (p+1)%K
    if D[n2] == -1:
        D[n2] = D[p] + 1
        q.appendleft(n2)
print(D[0])

Solution (Python):
import heapq
def main():
    k= int(input())
    brdict = {}
    for i in range(1,k):
        if i==k-1:
            if (10*(k-1))%k==0:
                brdict[i]= [(0,0)]
            else:
                brdict[i] = [(0,1)]
        else:
            if i!=(i*10)%k:
                brdict[i] = [((i*10)%k,0)]
            if (i*10)%k!=i+1:
                brdict[i] = brdict.get(i,[])+[(i+1,1)]
    start=1
    cost=[i for i in range(k)]
    cost[0]=k
    fixed=[False]*k
    fixed[start]=True
    akouho = [(1,start)]
    heapq.heapify(akouho)
    while not all(fixed):
        (fcost,fnode) = heapq.heappop(akouho)
        if fnode==0:break
        fixed[fnode]=True
        for br in brdict[fnode]:
            if not fixed[br[0]]:
                if cost[br[0]] > fcost + br[1]:
                    cost[br[0]] = fcost + br[1]
                    heapq.heappush(akouho,(cost[br[0]],br[0]))
        if akouho==[]:break
    print(cost[0])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
k=int(input())
g=[[] for i in range(k)]
for i in range(k):
  g[i].append(((i+1)%k,1))
  if i:
    g[i].append((10*i%k,0))
dq=deque([1])
res=[float('inf')]*k
res[1]=1
while dq:
  v=dq.popleft()
  if v==0:
    break
  for t,cost in g[v]:
    if res[t]<=res[v]+cost:
      continue
    res[t]=res[v]+cost
    if cost:
      dq.append(t)
    else:
      dq.appendleft(t)
print(res[0])

Solution (Python):
from collections import deque


K = int(input())
path = [K] * K

q = deque()
path[1] = 0
q.append(1)
while q:
    p = q.popleft()
    p1 = (p + 1) % K
    if path[p1] > path[p] + 1:
        path[p1] = path[p] + 1
        q.append(p1)
    
    p10 = (p * 10) % K
    if path[p10] > path[p]:
        path[p10] = path[p]
        q.appendleft(p10)

print(path[0] + 1)

Solution (Python):

from collections import deque
import sys
try:
    from typing import Deque, List
except ImportError:
    pass


def solve(K: int):
    pars = list(range(K))

    def union(a: int, b: int):
        pars[a] = b

    def getpar(a: int):
        if pars[a] == a:
            return a
        pars[a] = getpar(pars[a])
        return pars[a]

    for i in range(K):
        union(getpar(i), getpar(i * 10 % K))

    gs = [getpar(i) for i in range(K)]
    if gs[0] == gs[1]:
        print(1)
        return
    G = [[] for i in range(K)]  
    for i in range(K):
        G[gs[i]].append(gs[(i + 1) % K])
    d = {gs[1]: 1}
    q = deque()  
    q.append(gs[1])
    while q:
        s = q.popleft()
        for t in G[s]:
            if t in d:
                continue
            d[t] = d[s] + 1
            if t == gs[0]:
                print(d[t])
                return
            q.append(t)
    assert False


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    solve(K)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    def dijkstra(start,n,edges):
        d=[INF]*n
        used=[False]*n
        d[start]=0
        used[start]=True
        edgelist=[]
        for edge in edges[start]:
            heappush(edgelist,edge)
        while edgelist:
            minedge=heappop(edgelist)
            if used[minedge[1]]:
                continue
            v=minedge[1]
            d[v]=minedge[0]
            used[v]=True
            for edge in edges[v]:
                if not used[edge[1]]:
                    heappush(edgelist,(edge[0]+d[v],edge[1]))
        return d
    
    K=int(input())
    edges=[[] for _ in range(K)]
    for i in range(K):
        edges[i].append((1,(i+1)%K))
        edges[i].append((0,i*10%K))
    d=dijkstra(1,K,edges)
    print(d[0]+1)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def v(n):
        return [n*10%k, (n+1)%k]
    k = I()
    d = [float("inf")]*k
    d[1] = 1
    q = deque([1])
    while q:
        x = q.popleft()
        vx = v(x)
        dx = d[x]
        for c in range(2):
            nd = dx+c
            y = vx[c]
            if nd < d[y]:
                d[y] = nd
                if c:
                    q.append(y)
                else:
                    q.appendleft(y)
    print(d[0])
    return


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque
n = int(input())
mins = [1000 for i in range(n+1)]
used = [0 for i in range(n+1)]
deq = deque()
deq.append((1,1))
while deq:
  x,cnt = deq.popleft()
  mins[x] = min(mins[x],cnt)
  used[x] = 1
  if used[10*x%n] == 0:
    deq.appendleft((10*x%n,cnt))
  if used[(x+1)%n] == 0:
    deq.append(((x+1)%n,cnt+1))
print(mins[0])

Solution (Python):
from collections import deque
K = int(input())
cost = [-1] * K
deq = deque([(1,1)])
while deq:
    x, d = deq.popleft()
    if cost[x] >= 0: continue
    cost[x] = d
    if x == 0: break
    for y, c in [(10*x%K, 0), ((x+1)%K, 1)]:
        if c: deq.append((y, d + 1))
        else: deq.appendleft((y, d))
print(cost[0])

Solution (Python):
from collections import deque

K = int(input())

visited = [False] * K
Q = deque([(1, 1)])

while True:
    s, v = Q.popleft()
    if v == 0:
        print(s)
        quit()

    if visited[v]:
        continue
    visited[v] = True

    Q.appendleft((s, (10 * v) % K))
    Q.append((s + 1, (v + 1) % K))

Solution (Python):
from collections import deque
k=int(input())
t=[1]*k
q=deque()
q.append((1,1))
while q:
    p,r=q.popleft()
    if p==0:
        print(r)
        break
    if t[p]:
        t[p]=0
        q.appendleft(((p*10)%k,r))
        q.append(((p+1)%k,r+1))

Solution (Python):
from collections import deque
 

 
K = int(input())
q = deque()
q.append((1,1)) 
visited = [False]*K
 
ans = 0
 
while ans == 0:
  s,x = q.popleft()
  if visited[x]:
    continue
  visited[x] = True
  if x == 0:
    ans = s
    break
  q.appendleft((s,(10*x)%K))
  q.append((s+1,(x+1)%K))

print(ans)

Solution (Python):
K = int(input())
G = [[] for _ in range(K)]
for i in range(K):
    G[i].append((1, (i+1)%K))
    G[i].append((0, (i*10)%K))
from collections import deque
que = deque([1])
dist = [-1]*K
dist[1] = 0
"""while que:
    v = que.pop()
    d = dist[v]
    for nv, c in G[v]:
        if dist[nv]>=0:
            continue
        if c == 0:
            que.append(nv)
            dist[nv] = d
        else:
            que.appendleft(nv)
            dist[nv] = d+1
    print(que)"""
import heapq
inf = 10**10
def dijkstra(s, n, G):
    dist = [inf]*n
    edges = []
    dist[s] = 0
    for e in G[s]:
        heapq.heappush(edges, e)
    while edges:
        cost, v = heapq.heappop(edges)
        if dist[v] != inf:
            continue
        dist[v] = cost
        for c, nv in G[v]:
            if dist[nv] == inf:
                heapq.heappush(edges, (cost + c, nv))
    return dist
dist = dijkstra(1, K, G)
print(dist[0]+1)

Solution (Python):
from heapq import heappop,heappush 
from collections import deque
k=int(input())
inf=float("inf")
data=[[] for i in range(k)]
for i in range(1,k):
    if i%10==9:
        data[i]=[[i*10%k,0]]
    else:
        data[i]=[[i*10%k,0],[(i+1)%k,1]]

que=deque([[1,1]])
ans=[inf]*k
while que:
    c,u=que.popleft()
    ans[u]=c
    for v,d in data[u]:
        if ans[v]==inf:
            if d==0:
                que.appendleft([c,v])
            else:
                que.append([c+1,v])
    if ans[0]!=inf:
        break
print(ans[0])

Solution (Python):
K=int(input())

D=[K*10]*K
D[1]=1

import heapq

Q=[(1,1)]

while Q:
    c,x=heapq.heappop(Q)

    if D[x*10%K]>c:
        D[x*10%K]=c
        heapq.heappush(Q,(c,x*10%K))

    if D[(x+1)%K]>c+1:
        D[(x+1)%K]=c+1
        heapq.heappush(Q,(c+1,(x+1)%K))

print(D[0])