[BOJ] 12779 상품 is 뭔들

문제 링크

www.acmicpc.net/problem/12779

풀이

약수의 개수가 홀수라는 뜻은 어떤 자연수를 제곱한 제곱수라는 뜻이다.
따라서, $a$와 $b$ 사이에 존재하는 제곱수의 개수를 세면 된다.

Java 코드

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

public class Main {
    static long gcd(long a, long b) {
        return b > 0 ? gcd(b, a % b) : a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        int cnt = (int) Math.sqrt(b) - (int) Math.sqrt(a);

        if (cnt == 0) {
            System.out.println(0);
            return;
        }

        long g = gcd(cnt, b - a);
        System.out.println(cnt / g + "/" + (b - a) / g);
    }
}