정수론 문제 - 나머지 연산을 꼭 기억하고 있어라

1. 문제

 

4375번: 1 (acmicpc.net)

4375번: 1

 

2. 풀이1

 

문제는 n의 배수인, 1로만 이루어진 수 중에서 자리수가 가장 작은 수를 찾는 문제

 

아주 단순하게는 n보다 큰 1로만 이루어진 수를 생성한 다음에.. 그 수가 n으로 나누어 떨어지는지 검사해보면 된다

 

n의 길이를 i라 한 다음에... 1로만 이루어진 길이 i인 수부터 시작해서.. n으로 나누어가지고

 

가장 먼저 나누어 떨어지는 수를 출력

 

from sys import stdin

while 1:
    
    try:

        n = int(stdin.readline())

        i = len(str(n))

        x = int('1'*i)

        while x % n != 0:
            
            i += 1

            x = int('1'*i)
        
        print(i)

    except:
        
        break

 

 

2초나 걸린단 말이지.. string을 int로 바꾸는게 시간복잡도가 생각보다 엄청 크다..

 

string이 immutable이다 보니 string repetition도 시간복잡도가 클거고

 

큰 수의 modulo 연산도 시간복잡도가 클거임

 

 

3. 풀이2

 

정수론에서 아주 강력한 무기 중에 하나가 바로 "나머지"

 

https://deepdata.tistory.com/399

정수론 - 합과 곱은 왜 계속 나눠도 문제가 없는가? -

 

"a를 n으로 나눈 나머지와 b를 n으로 나눈 나머지의 곱을 n으로 나눈 나머지는 a*b를 n으로 나눈 나머지와 같다."

 

"a를 n으로 나눈 나머지와 b를 n으로 나눈 나머지의 합을 n으로 나눈 나머지는 a+b를 n으로 나눈 나머지와 같다"

 

 

그리고 배수인지 판정할려면?

 

1로 이루어진 수를 n으로 나눈 나머지가 0인지 아닌지만 검사하면 된다.

 

따라서 1로 이루어진 수를 생성하지 말고, 나머지만 저장해둔다면... 작은 수에 대한 연산으로 시간복잡도를 줄일 수 있다.

 

여기서 1로 이루어진 수를 생성할려면 어떻게 해야할까?

 

길이 i에 1을 더하고 '1'*i를 하는게 아니라,

 

이전 수 x에 10을 곱하고, 1을 더해주면 된다.

 

from sys import stdin

while 1:
    
    try:

        n = int(stdin.readline())

        i = len(str(n))
        
        #x를 1로 이루어진 수를 n으로 나눈 나머지로 정의
        x = int('1'*i) % n

        while x != 0:
            
            #10을 곱하고, 1을 더하면 뒤에 1을 붙이는거나 다름없다
            x *= 10
            x += 1
            
            #자리수가 1 증가
            i += 1
            
            #x를 n으로 나눈 나머지로 저장
            x %= n
        
        #나머지가 0이 되는 순간 반복문 탈출하고, 길이 i를 출력
        print(i)

    except:
        
        break

 

 

 

4. 문제2

 

1612번: 가지고 노는 1 (acmicpc.net)

1612번: 가지고 노는 1

 

5. 풀이

 

똑같은 문제이기 때문에 n으로 나눈 나머지를 저장하면서.. 10을 곱하고 1을 더한 다음에

 

n으로 나눈 나머지가 0인지 아닌지 검사하고 가장 먼저 나머지가 0이 된다면 그 자리수를 출력

 

조금 더 어렵다면.. 일단 불가능한 경우 -1을 출력하라고 한다.

 

n의 배수중에 1만으로 이루어진 수가 없는지 알수가 있나?

 

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

 

1로만 이루어진 수 x를 n으로 나눈 나머지가 a일때

 

다음에는 a*10 + 1을 n으로 나눈 나머지가 b가 되고..

 

다음에는 b*10 + 1을 n으로 나눈 나머지가 c가 되고...

 

이 과정을 반복하다가 나머지가 0인 경우가 나온다면.. 그때 수의 자리수를 출력하면 되는데

 

이 과정을 반복하는데 0인 경우가 존재하지 않고 이전에 나왔던 나머지가 나온다면 불가능한 경우다.

 

왜냐하면.. 나머지에 10을 곱하고 1을 더한 다음에 n으로 나누는 과정이 반복되잖아..

 

그러니까 이전에 나온 나머지 r이 또 나온다면.. 사이클이 계속 반복될거잖아

 

from sys import stdin

n = stdin.readline().rstrip()

len_n = len(n)

n = int(n)

r = int('1'*len_n) % n

period = [0]*n

period[r] = 1

while r != 0:

    r *= 10
    r += 1
    len_n += 1

    r %= n
    
    period[r] += 1
    
    if period[r] >= 2:
        len_n = -1
        break

print(len_n)

 

수학적으로 위 과정을 증명해보자.

 

서로 다른 두 정수 a < b < n에 대하여.. 

 

(a*10+1)%n = (b*10+1)%n != 0을 만족한다면.. 이전에 나온 나머지가 반복되는 경우이다.

 

위 식을 푼다면.. 어떤 자연수 c에 대하여... cn + 10a+1 = 10b+1

 

10(b-a)/c = n

 

여기서 n이 자연수일려면... c가 10의 약수이거나, b-a의 약수이다.

 

c가 b-a의 약수이면.. n은 10의 배수이다.

 

c가 10의 약수이면..,. c는 1,2,5,10인데.. c = 10이면.. b-a = n인데 a<b<n이므로 불가능하다.

 

따라서 c는 1,2,5가 가능한데.. 그런 경우 n은 각각 10,5,2의 배수가 된다.

 

따라서 n이 10의 배수이거나 2의 배수이거나 5의 배수이면 끝자리가 1인 숫자들의 배수가 될 수 없다.

 

10의 배수는 2의 배수이면서 5의 배수이기도 하니까... n이 2의 배수이거나 5의 배수이면 끝자리가 1인 숫자들의 배수가 될 수 없다.

 

사실 이전 문제는 2와 5의 배수가 아닌 n이라고 가정했는데.. 이런 이유 때문이다.

 

from sys import stdin

n = stdin.readline().rstrip()

len_n = len(n)

n = int(n)

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

else:

    r = int('1'*len_n) % n

    while r != 0:
        
        r *= 10
        r += 1
        len_n += 1

        r %= n

    print(len_n)

 

 

https://kimcodingvv.github.io/BOJ-1612/

[BOJ | 백준] 1612번: 가지고 노는 1