문자열 파싱을 이상하게 시도해서 애먹었던 문제입니다..
가장 단순히 보이는 풀이는 나오는 모든 수를 곱하거나 나누어서 마지막에 유리수 판정을 하는 것입니다.
하지만 최대 100,000 ^ 100,000 인 수를 변수에 저장할 순 없을 것입니다. 가능하더라도 나눗셈이 나오면 무한소수가 아오는 등 정확한 값을 저장할 수 없기 때문에 다른 방법을 생각해 보아야 합니다.
우리는 각 숫자를 더하거나 나눌때 이 수를 나누어서 저장하고 계산할 방법이 필요합니다. 이 수를 어떻게 잘 저장할 수 있을까요?
정답은 바로 소인수분해 입니다. 만약 수를 소인수분해한 형태로 저장하면 관리하기도 쉽고, 마지막에 유리수 판정을 할 때도 간단하게 할 수 있습니다.
그럼 소인수분해는 어떻게 하면 될까요? 기본적으로는 소수를 구해 계속 나눠보면 되겠지만 그러면 시간초과가 납니다. 만약 F(x)를 1이 아닌x의 가장 작은 소인수라고 저장해 놓면, 계속 수를 F(x)로 나누면 쉽게 소인수 분해가 가능할 것입니다. 이때 각각의 F(x)를 일일이 구하는 것이 아니라 거꾸로, 그러니까 2로부터 2의 배수를 F(x)에 저장해놓면 쉽게 구현을 할 숫 있을 것입니다.