안녕하세요,
재재입니다.
BOJ 4355 서로소 문제 풀이입니다.
BOJ 4355 서로소
(1) 문제 설명
분류 : math, 포함배제원리
출처 : https://www.acmicpc.net/problem/4355
(1,000,000,000 이하) n 이 주어집니다.
n 보다 작은 양의 정수 중 n과 서로소인 수의 갯수를 구해주면 됩니다.
(2) 풀이 도출
예를들어 n 을 12라고 한다면,
12의 서로소는 아래와 같이 나열 할 수 있습니다.
$$ 1, 5, 7, 11 $$
자세히 보면, 2의 배수이거나 3의 배수인 경우의 숫자가 제외되어있습니다.
다른 숫자를 더 써보면 알 수 있지만,
이 문제의 핵심은 n 을 소인수 분해하는 것입니다.
n 보다 작은 숫자 중 2의 배수의 갯수는 $$ (n-1) / 2 $$ 와 같고,
n 보다 작은 숫자 중 3의 배수의 갯수는 $$ (n-1) / 3 $$ 과 같습니다.
여기서 6이 2번 겹쳤기 때문에, 이를 반영해주면 됩니다. (포함 배제 원리)
사용되는 인자의 갯수가 홀수개인지,
짝수개인지에 따라 방법을 달리 할 수 있습니다.
(3) 정답 코드
BOJ 4355 서로소