시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 3562 | 738 | 486 | 21.941% |
자연수 N이 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 수 중에서 N과 서로소인 것의 개수를 구하는 프로그램을 작성하시오.
두 정수를 나눌 수 있는 양의 정수가 1밖에 없을 때, 두 정수를 서로소라고 한다. 즉, 두 수의 최대공약수가 1이면 서로소이다. 1은 모든 정수와 서로소이다.
첫째 줄에 테스트 케이스의 개수 T (0 < T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 1015, 1 ≤ N ≤ 109)
각 테스트 케이스마다 A보다 크거나 같고, B보다 작거나 같은 자연수 중에서 N과 서로소인 것의 개수를 출력한다.
2 1 10 2 3 15 5
Case #1: 5 Case #2: 10
[1,10]에 속하는 수 중에서 2와 서로소인 것은 {1, 3, 5, 7, 9}이다.