응애개발자
article thumbnail
728x90

문제

https://www.acmicpc.net/problem/2725

 

접근 방법

  1. (x,y) 점이 주어졌을 때 0,0 에서 보이는 점의 개수를 구하는 문제입니다.
  2. 예를들어 (1,1), (2,2), (3,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);
    }
}
profile

응애개발자

@Eungae-D

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!