프로그래민👨‍💻

생각하기 어려운 수학문제였다. 단순히 생각해서 N개의 소세지를 전체 이어붙이고 M개로 만들기 위해선 (M-1)번의 칼질이 필요하다는 것을 알 수 있다. 하지만 N이 M으로 나눠지거나 M이 N으로 나눠지는 경우 생각하지 않아도 되는 칼질의 경우가 생기는 것을 알 수 있다. 이것을 위해 최대공약수로 나누어 답을 구한다면 (M/GCD - 1) 번의 칼질이 나오는데 이것을 다시 GCD로 곱해야지 최종 답을 알 수 있다. 즉, 칼질횟수 = GCD(M/GCD - 1) = M - GCD 임을 알수가 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 package study4; import java.io.BufferedReade..

소수를 구하는 방법은 크게 두가지가 있다. 1. 어떤수 N이 소수인지 판별하는 방법 특정수 N이 소수인지 확인하기 위해 i=2부터 i*i

간단해보이는 문제지만 다양한 개념들이 사용된 문제이다. 다음과 같은 개념들이 사용되었다. 모듈러연산의 특징 모듈려는 /을 제외한 +, -, * 에 대해서 다음과 같은 특징을 가진다. (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 합동관계 두 a, b숫자가 n을 mod한 결과 값이 같다면 모듈러 합동관계라 한다. 즉, a mod n = b mod n의 관계를 a ≡ b (mod n)으로 표현할 수 있다. 페르마의 소정리 p가 소수이고 a가 p로 나누어지지 않는 정수이면 다음과 같은 특징을 가진다. a^p ≡ a (mod p) a^..