테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 숫자 연결하기 ======

===== 풀이 =====
  * 우선 기본적인 것부터.. N가 a자리 수라고 하면, 어떤 수 x 뒤에 N를 한번 더 이어붙인 수는 x*(pow(10,a))+N가 된다.
  * 그래서 N을 i번 이어붙인 수를 K로 나눈 나머지가 r 이라면, N을 (i+1)번 이어붙인 수를 K로 나눈 나머지는 (r*(pow(10,a))+N) % K 가 된다.
  * 이렇게 큰 수 연산 없이도, N을 i번 이어붙인 수가 K로 나누어 떨어지는지 확인할 수 있게 되었다. 이제 나누어 떨어질 때까지 반복해서, 몇번 이어붙였을때 나누어 떨어지는 지를 확인하면 된다. 
  * 반복횟수의 상한은 [[ps:tutorial:PHP]]를 이용해서 구하면 된다. i+1번째의 나머지값은 i번째의 나머지값에 의해서만 결정되고, 나머지값의 종류는 K가지이다. 따라서, 최대 K+1번 반복하면 이미 나왔던 상태로 다시 돌아가게 될것이고, 거기서부터 사이클이 생겨서 다시 똑같은 값들만 갖게 될것이다. 그러므로, 반복하다가 나머지가 0이 되기 전에, 사이클이 생기게 되면 답이 없음을 출력하고 종료하면 된다. 이러면 K번 이내의 반복으로 작업을 마칠수 있다. 
  * 사이클이 생기는 것을 찾기 위해, 나왔던 값들을 트랙하는것조차 귀찮다면, 그냥 K번 반복을 돌리고 그때까지 나머지값이 0이 되는 경우가 없다면 그냥 답이 없음을 출력해도 충분하다.
  * 시간복잡도는 O(K)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1323. 숫자 연결하기".

- Problem link: https://www.acmicpc.net/problem/1323
- Solution link: http://www.teferi.net/ps/problems/boj/1323

Tags: [PHP]
"""


def main():
    N, K = [int(x) for x in input().split()]

    x = 10 ** len(str(N))
    rem = 0
    for i in range(1, K + 1):
        rem = (rem * x + N) % K
        if rem == 0:
            print(i)
            break
    else:
        print('-1')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}