[BOJ] 1612 - 가지고 노는 1

문제 링크

나머지 연산에 대해 많은 생각을 하게 해준 문제.
처음에는 4375-1문제와 같은 방식으로 풀리지 않을까 하여 바로 내봤는데, 틀렸습니다를 받았다.
그래서 아 이건 수학문제구나 하고 한참 삽질을 했더랬다. 1로만 이루어진 수의 규칙이나.. 소인수분해 결과를 보며 머리를 끙끙 싸매다가 결국 구글링을 통해 해답을 알아냈다.
이전 풀이 방법처럼 자리수를 하나씩 늘려가며 탐색하되, 수의 크기가 너무 커지지 않게 하는 것이 핵심이었다.
사실 수의 크기가 커지지 않게 하라는 힌트는 이미 질문 검색 게시판에서 봤었는데, 방법에 대해 전혀 생각해내지 못했다.. 아직 많이 부족하다
풀이 방법은 다음과 같다.
아이디어 : 1로 이루어진 수를 주어진 수로 나누어 나머지가 0이 되면 정답을 찾은것이므로 자리수를 출력한다.
응용 : (Ax10+1)%B = ((A%B)x10+1)%B임을 이용하여, 갱신하면서 A의 크기가 B보다 커지지 않도록 나머지 연산을 통해 갱신해준다.

소스코드

import sys
def input(): return sys.stdin.readline().rstrip()

n = int(input())

if not n%2 or not n%5:
    print(-1)

else:
    ans=1
    now = 1
    while now % n:
        now = (now % n)*10+1
        ans+=1
    print(ans)