[백준 - 17355번] Messi An-Gimossi - Java //Wello Horld//

이번에는 BOJ의 17355번 문제 "Messi An-Gimossi"를 풀어보도록 하자

처음 이 문제를 딱 봤을 때, "모듈러 연산으로 풀면 되겠네!! 간단하네!!" 라고 생각하고, 이틀동안 문제가 안풀려서 끙끙 앓았다. 결국에 풀긴 했는데, 아래 코드보다 더 연산을 빠르게 할 수 있는 것 같아서 이 부분에 대해서는 더 생각해 봐야 될 것 같다.

이 문제를 풀기 위해서, 크게 3부분으로 나눠서 프로그램을 만들었다

• 소인수 분해를 통해서 분자, 분모가 서로소가 되도록 소인수들을 저장해 줄 HashMap<Long, Long> 을 만들어줌
• 입력되는 값을 소인수 분해 해줘서, A를 소인수분해한 값이 map의 음수부(-)에 있으면 지워주고, B를 소인수 분해한 값이 map양수부(+)에 있으면 지워줌
• map에 남아있는 것을 음수부(-)와 양수부(+)로 나눠서 각각 다 곱해준 값을 a, b라고 하면 a와 b는 서로소이기 때문에, 서로 상관없이 모듈러 연산으로 답을 구해줌

성공한 코드는 아래와 같다.

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

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        long a, b;
        long m = 1000000007L;
        HashMap<Long, Long> map = new HashMap<Long, Long>();
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            a = Long.parseLong(st.nextToken());
            b = Long.parseLong(st.nextToken());
            a = b - a;
            for(long j = 2; j * j <= a; j++){
                if(a % j == 0){
                    if(map.get(-j) != null && map.get(-j) != 0){
                        map.put(-j, map.get(-j) - 1);
                    } else {
                        if(map.get(j) != null && map.get(j) != 0){
                            map.put(j, map.get(j) + 1);
                        } else {
                            map.put(j, 1L);
                        }
                    }
                    a /= j;
                    j--;
                }
            }
            if(a > 1) {
                if(map.get(-a) != null && map.get(-a) != 0){
                    map.put(-a, map.get(-a) - 1);
                } else {
                    if(map.get(a) != null && map.get(a) != 0){
                        map.put(a, map.get(a) + 1);
                    } else {
                        map.put(a, 1L);
                    }
                }
            }

            for(long j = 2; j * j <= b; j++){
                if(b % j == 0){
                    if(map.get(j) != null && map.get(j) != 0){
                        map.put(j, map.get(j) - 1);
                    } else {
                        if(map.get(-j) != null && map.get(-j) != 0){
                            map.put(-j, map.get(-j) + 1);
                        } else {
                            map.put(-j, 1L);
                        }
                    }
                    b /= j;
                    j--;
                }
            }
            if(b > 1) {
                if(map.get(b) != null && map.get(b) != 0){
                    map.put(b, map.get(b) - 1);
                } else {
                    if(map.get(-b) != null && map.get(-b) != 0){
                        map.put(-b, map.get(-b) + 1);
                    } else {
                        map.put(-b, 1L);
                    }
                }
            }
        }
        a = 1L;
        b = 1L;
        for(Map.Entry<Long, Long> selects : map.entrySet()){
            long key = selects.getKey();
            long value = selects.getValue();
            if(key >= 0){
                for(int i = 0; i < value; i++){
                    a *= key;
                    a %= m;
                }
            } else {
                for(int i = 0; i < value; i++){
                    b *= -key;
                    b %= m;
                }
            }
        }
        long remainA = a % m, remainB = b % m;
        bw.write(remainA + " " + remainB + "\n");

        bw.flush();
        br.close();
        bw.close();
    }
}

 

문제 : https://www.acmicpc.net/problem/17355

17355번: Messi An-Gimossi