개발일지

개념 오일러의 피 함수는 N이 주어 졌을 때 1 ~ N의 숫자중 N과 서로소인 숫자의 개수를 찾는 함수이다. 작동원리 1. p가 소수인 경우 소수인 경우 약수가 1과 자기 자신밖에 없으므로 자기 자신을 제외한 모든 수와 서로소이다. 2. 소수 p의 거듭제곱인 경우 소수 p의 거듭제곱과 서로소가 아닌 경우는 p의 배수일 경우이다. 즉 p, 2p, 3p .... p^(k-1) * p => p^k - p^(k-1)이다. 3. n과 m이 서로소인 경우 n과의 서로소의 곱과 m과 서로소의 곱은 n*m과 서로소이다. 결론 n을 소인수 분해했을 때 p1^a1 * p2^a2 * p3^a3 ... pn^an꼴이 나오면 다음이 성립한다. 문제 www.acmicpc.net/problem/11689 11689번: GCD(n,..

개념 최대 공약수를 쉽게 구하는 방법 작동원리 ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 ko.wikipedia.org 시간복잡도 O(1) 문제 www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가..