원점에서 보이는 점의 개수
시간 제한1초메모리 제한128 MB
0<=x,y<=N 범위에서 원점에서 직선으로 가려지지 않고 보이는 격자점, 즉 gcd(x,y)=1인 점의 개수를 구하는 문제입니다.
문제
좌표평면의 정수 격자점 (x, y) 중 0 <= x, y <= N을 만족하는 점을 생각하자. 단, 원점 (0, 0)은 세지 않는다.
원점에서 점 (x, y)가 보인다는 것은 원점과 (x, y)를 잇는 선분이 다른 정수 격자점을 지나지 않는다는 뜻이다. 예를 들어 (4, 2)는 원점에서 보이지 않는다. 원점과 (4, 2)를 잇는 선분이 (2, 1)을 지나기 때문이다.
자연수 N이 주어질 때, 원점에서 보이는 점 (x, y)의 개수를 구하시오.
입력
첫째 줄에 테스트 케이스의 개수 C가 주어진다. 1 <= C <= 1,000이다.
다음 C개의 줄에는 테스트 케이스가 한 줄에 하나씩 주어진다. 각 테스트 케이스는 자연수 N 하나로 이루어져 있으며, 1 <= N <= 1,000이다.
출력
각 테스트 케이스마다 원점에서 보이는 점 (x, y)의 개수를 한 줄에 하나씩 출력한다.