Modular Arithmetic (모듈로 연산) - PYTHON(백준 #4375)
모듈로 연산 : 나머지 연산
: 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산
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