카테고리 없음

Modular Arithmetic (모듈로 연산) - PYTHON(백준 #4375)

MoveForward 2022. 3. 13. 16:07

모듈로 연산 : 나머지 연산 

: 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산

 

Ex)

7 mod 3 = 1

17 mod 5 = 2

19 mod 7 = 5

 

 

 

a ≡ b (mod n)  <=>  b ≡ a (mod n)

a ≡ b (mod n)  and  b ≡ c (mod n)  =>  a =c 

 

(a + b) mod n = ((a mod n) + (b mod n)) mod n

(a - b) mod n = ((a mod n) - (b mod n)) mod n

(a * b) mod n = ((a mod n) * (b mod n)) mod n

 

교환

(a + b) mod n = (b+a) mod n

(a * b) mod n = (b * a) mod n

 

결합

((a + b) + c) mod n = (a + (b + c)) mod n

((a * b) * c) mod n = (a * (b * c)) mod n

 

분배

(a * (b + c)) mod n = ((a * b) + (a * c)) mod n

 

 

EX)

214 mod 3

= 100 * 2 + 14

= 20 * 5 * 2 + 14

= 2 * 2 * 2 + 2

= 8 + 2

= 2 + 2

= 4

= 1

= 1 mod 3

 

 

# 백준 4375

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

# 백준 4375
while True:
    try: 
        n = int(input())
    except:
        break
        
    div=0
    i=1 # 자리수 카운트
    while True:
        div = div * 10 + 1
        
        # modular 연산에 의해..
        div %= n # 나머지를 다시 div에 저장
        
        if div == 0:
            print(i)
            break
        i+=1

111111 mod 7

= 1 + 10 + 100 + 1000 + 10000 +100000

= 1 + 3 + 3^2 + 3^3 + 3^4 + 3^5

= 1 + 3 + 2 + 6 + 4 + 5

= 6 + 15

= 6 + 1

= 7 

= 0 

= 0 mod 7