나머지 연산과 비둘기집 원리

1323번: 숫자 연결하기

 

어떤 수 n,k가 주어질때, n을 여러번 붙여써서 k로 나누어지는 경우가 있는지 알고 싶다

 

예를 들어 10은 1번 쓰면 10

 

2번 쓰면 1010

 

3번 쓰면 101010

 

이때, 최소로 붙여써서 k로 나누어 떨어지게 하고 싶을때 최솟값을 구한다면?

 

------------------------------------------------------------------------------------------------------------------------------------------------------

 

n을 여러번 붙여쓴다는 것은

 

예를 들어 10을 여러번 붙여쓴다면 1번 쓰는 경우 10, 2번 쓰는 경우 1010인데

 

1010 = 1000 + 10 = 10*10^2 + 10

 

즉 10의 길이만큼 0을 뒤에 붙이고 10을 더해주는 식으로 더해진다

 

비슷하게 3번 쓰면 101010 = 100000 + 1000 + 10 = 10*10^4 + 10*10^2 + 10 = 10*(10^4+10^2+10^0)

 

k번 붙여쓴다면 10*(10^2*(k-1) + 10^2*(k-2) + ... + 10^2+10^0)

 

n을 k번 붙여쓴다면 n*(10^len(n)*(k-1) + ... + 10^len(n) + 10^0)

 

따라서 n*(10^len(n)*(k-1) + ... + 10^len(n) + 10^0)을 k로 나누어서 떨어지는지 확인해봐야함

 

n을 k로 나눈 나머지 구하고

 

10^len(n)*m은 pow를 이용해서 빠른 거듭제곱으로 나머지 구하고

 

붙여쓰는 횟수 m을 1번씩 늘려가면서 k로 나누어보고 

 

n,k = map(int,input().split())

r1 = n % k
r2 = 0

n = str(n)
m = 0

period = set()

while 1:
    
    r2 += pow(10,m*len(n),k)
    r2 %= k

    r = (r1*r2)%k

    if r == 0:
        
        break
    
    else:
        
        if r in period:
            
            m = -2
            break
        
        else:

            period.add(r)

    m += 1

print(m+1)

 

 

근데 언제 멈춰야할지가 문제임

 

그래서 그냥 period에 나머지들을 저장해두고 이전에 나온 나머지가 또 나오면 멈추도록 했는데

 

이게 맞나 싶더라고

 

주기라는게 이전에 나온게 나온다고 그게 아니라

 

3 3 4 4까지 나오다가 3이 나온다고 이게 주기가 성립하고 있는지 모르는거니까 흠

 

----------------------------------------------------------------------------------------------------------------------------------------------------------

 

근데 나머지라는것을 잘 생각해보면 k로 나눈 나머지는 0~k-1중 하나이다

 

그러니까 가능한 나머지는 최대 k개의 나머지만 나온다는 뜻인데 그러므로 비둘기집의 원리에 따라

 

k+1번 k로 나누는 연산을 반복하면 무조건 2개 이상 같은 나머지가 나오게된다

 

따라서 나누는 연산은 최대 k번만 하면 충분하다

 

그 안에 나머지가 0이 안되면 무조건 0이 안된다

 

n,k = map(int,input().split())

r1 = n % k

n = str(n)

r2 = 0

answer = -1

for i in range(1,k+1):

    r2 += pow(10,len(n)*(i-1),k)
    r2 %= k

    if (r2*r1) % k == 0:
        
        answer = i
        break

print(answer)