[백준] 12779번 - 상품 is 뭔들 [Java]

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

 

[백준] 12779번 - 상품 is 뭔들 [Java]

---

1.  아이디어

 

약수의 개수가 홀수인 숫자는 제곱수라는 점을 활용한다.

---

2. 문제풀이

 

4, 9, 16 같은 제곱수만 약수의 개수가 홀수가 되므로 해당 범위에 포함된 제곱수를 찾은 후 유클리드 호제법으로 기약분수로 출력하는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        long N = 0;
        for (long i = (long) Math.sqrt(A); i * i <= B; i++) {
            if (A < i * i && i * i <= B) N++;
        }

        if (N == 0) {
            sb.append(0);
        } else {
            long gcd = gcd(N, B - A);
            sb.append(N / gcd).append("/").append((B - A) / gcd);
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

}

---

4. 후기