곱을 직접 하지 마시고, 다른 적당한 표현으로 나타내 보세요. 이를테면 105를 3×5×7로 나타내는 것처럼요. 약분을 하기 좋은 형태라면 더 좋겠죠?

아직 풀어보지는 않았습니다만,

1.(a₁ * a₂ * a₃ * ... * a_n) % m 을 구하고 싶을때, 굳이 다 곱한후 나머지 연산을 할 필요는 없습니다. (a * b) % m = ((a % m) * (b % m)) % m을 만족하기 때문입니다.

2. A, B 둘 다 10^7 이하이기 때문에, A, B의 소인수도 10^7 이하입니다. 그 말은, 구한 확률을 A' / B'이라고 했을때 A', B'의 소인수도 10^7 이하라는 뜻입니다.

3. 소인수 분해는 에라토스테네스의 체를 조금 응용해서 S(n) = n의 가장 작은 소인수 을 미리 구해놓으면 꽤 효율적이게 할 수 있습니다.

시간 초과는 안날것 같은데 잘 모르겠네요

소인수 분해로 약분을 해주면서, 

남은 소인수들을 마지막에 곱해주고 동시에 모듈러 연산을 통해 연산을 줄이도록 했습니다. 

될법한데 또 시간초과가 떠버렸습니다. 계속 해보고 있긴한데, 오늘도 먹먹하네요

"소인수 분해로 약분을 해주면서, 남은 소인수들을 마지막에 곱해주고 동시에 모듈러 연산을 통해 연산을 줄이도록 했습니다." 방식으로 작성한 소스 코드를 올려주세요

아래와 같이 크게 3부분으로 나눠서 프로그램을 만들었는데, 먼저 HashMap<Long, Long> 을 2개 만들어주고,

입력되는 값을 소인수 분해 해줘서, A를 소인수분해한 값이 mapB에 있으면 지워주고, B를 소인수 분해한 값이 mapA에 있으면 지워줬습니다.

그리고 마지막으로 mapA 와 mapB에 남아있는 것을 각각 다 곱해준 값을 a, b라고 하면 a와 b는 서로소이기 때문에, 서로 상관없이 모듈러 연산으로 답을 구하는 방식을 택했습니다.

올리신 코드의 입출력 부분을 스스로 작성해서 붙인 후 제출했을 때 "맞았습니다!!" 를 받았습니다. (5760ms)

참고로 JAVA 언어로 작성했을 때 이 문제의 시간 제한은 6000ms 입니다.

작성하신 소스 코드의 일부만 올리시는 것은 원인을 찾기 매우 힘들어지며 올린 코드가 아닌 다른 부분에 원인이 있을 가능성도 있기 때문에 권장하지 않습니다.

작성하신 전체 코드를 올려주세요.

도움을 주셔서 대단히 감사합니다. 

당시에 제출했던 전체 코드를 올려드립니다.

현재 작성하신 코드는 문제에서 의도했던 해법에 매우 가깝습니다. 입출력 코드에서도 특별히 문제될 점은 없는 것으로 보입니다.

다만, 이 프로그램의 수행 시간의 변동폭이 상당히 큰 것 같습니다.

이 알고리즘을 쓰는 형태로 총 5번 제출해 본 결과, 5488ms, 5628ms, 5760ms, 시간초과, 시간초과 결과를 받았습니다.

앞서 말씀드렸다시피 이 문제에서 Java 프로그램의 제한 시간이 6000ms 이며, 서버의 상황에 따라 이 제한을 넘기기도 하고 아니기도 하는 것 처럼 보입니다.

만약 시간을 확실히 줄이고 싶다면 다음 방법을 사용할 수 있습니다:

자료구조에 대해 좀 더 고민해 보면 mapA 와 mapB 를 하나의 자료구조로 합칠 수 있습니다. 예를 들어 분자를 양수로, 분모를 음수로 저장하는 건 어떨까요?

시간초과 두번뜨고 나서 안되는 줄 알고 안해봤는데, 접근법이 맞았다니 정말 다행이네요.

자세하게 설명해주시고 잘 알려주셔서 대단히 감사합니다.

이틀동안 뇌 터지는 줄 알았는데, 덕분에 편하게 잠잘 수 있게 됐네요

아 그리고 map을 하나로 만드는 방법은 생각지도 못했어서 아주 큰 도움이 됐습니다.

이후에도 여러 방법으로 활용할 수 있을 것 같네요

다시 한번 감사드립니다^^