728x90
문제
https://www.acmicpc.net/problem/2725
접근 방법
- (x,y) 점이 주어졌을 때 0,0 에서 보이는 점의 개수를 구하는 문제입니다.
- 예를들어 (1,1), (2,2), (3,3) 이렇게 3개의 좌표는 같은 선분이므로 보이지 않습니다.
- 따라서 기울기가 겹치지 않는 (기울기의 최대공약수가 1인 선분) 값을 찾아서 두개씩(좌표를 대각선으로 잘랐을때 겹치므로) 더해주면 됩니다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static StringBuilder sb;
private static BufferedReader br;
private static StringTokenizer st;
private static int T,N;
private static int[] arr = new int[1010];
//최대공약수
public static int gcd(int i, int j){
while(i%j != 0){
int temp = i%j;
i = j;
j = temp;
}
return j;
}
//입력
public static void input() throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
arr[1] = 3;
for(int i = 2 ; i <= 1000 ; i++){
int cnt = 0;
for(int j = 1 ; j < i ; j++){
if(gcd(i,j) == 1){
cnt+=2;
}
}
arr[i] = arr[i-1]+cnt;
}
for(int tc = 0 ; tc < T ; tc++){
N = Integer.parseInt(br.readLine());
process();
}
}
//실행
public static void process() {
sb.append(arr[N]).append("\n");
}
public static void main(String[] args) throws Exception {
input();
System.out.println(sb);
}
}
'코딩테스트 > 백준' 카테고리의 다른 글
[Java] 백준 1407번 : 2로 몇 번 나누어질까 (0) | 2024.05.17 |
---|---|
[Java] 백준 2436번 : 공약수 (0) | 2024.05.14 |
[Java] 백준 15736번 : 청기 백기 (0) | 2024.05.14 |
[Java] 백준 18110번 : solved.ac (0) | 2024.05.10 |
[Java] 백준 15829번 : Hashing (0) | 2024.05.10 |