1 ≤ R, G ≤ 1,000,000,000이란 말은 R, G 두 수 모두 1,000,000,000 이하라는 말입니다.

여기서 두 수의 최대공약수도 1,000,000,000 이하이므로 O(최대공약수)의 시간복잡도를 가지면 TLE가 나게 됩니다.

(어떤 수)의 약수(여기서는 최대공약수의 약수)를 구하는 방법은 루트(어떤 수) 만에 할 수 있습니다.

예를 들어 20의 약수를 생각해봅시다. 1, 2, 4, 5, 10, 20이 있습니다.

이는 달리 표현하면,  1, 2, 4, 20/4, 20/2, 20/1이 됩니다.

여기서 뭔가가 보이시나요?

1 ~ 루트(어떤 수) 까지 중 20의 약수인 것들을 Xi라 하면, (어떤 수)/Xi한 것들이 대칭적으로 약수가 되게 됩니다.

단 주의할 부분은 (어떤 수)/Xi 와 Xi가 같은 경우인데, 이 경우는 (어떤 수)가 제곱수일 경우 생기며, 하나만 반영해주시면 됩니다. (16의 약수는 1, 4, 16/4, 16/1인데 4와 16/4는 같으므로 실제 약수는 1, 4, 16)

두 수의 최대공약수의 루트 만큼의 시간복잡도를 가지면 되므로 O(루트(1000000000))에 해결할 수 있습니다.

아.. O(루트) 만큼의 시간복잡도가 가능하군요.. 최대공약수로만 생각하려다보니 제 머리가 굳어버렸었네요..

두분 모두 감사드립니다!

아, 머리가 굳었다는건 제머리가 이미 굳어버렸다는게아니고

최대공약수로만 문제를 해결하려다보니 그쪽으로밖에 머리가 안돌아가게 됬었다는 의미이지 결코 제자신의 한계를 결정한것이 아니에요.

문제도 거의 해결단계까지 왔습니다.

답변 감사드려요 ㅎㅎ

@js7309

두 수를 1,000,000,000 으로 넣으면 최대공약수 또한 1,000,000,000 이기때문에

그냥 그렇게 해선 안되는거같아요. 실제로 제가 사용한 방법도 저 소스와 같은 알고리즘이었지만 시간 초과가 났네요.

지금은 무사히 해결됬습니다 ㅎㅎ

아래소스는 어떤분이 맞추신 소스인데 최대공약수를 이용하는 방법이더군요. 최대공약수를 2로 나눈다는 발상은 못해봤는데

신기하다고 생각했습니다. 

자바로 하면 그렇게 해도 되는군요..

저는 똑같은 알고리즘으로 c로 코딩했는데 시간 초과가 났습니다.

최대공약수를 저렇게 구하면 시간 초과가 날 수 있습니다

a가 b보다 매우 크면, 시간이 매우 오래 걸립니다.

1년전 글이지만, 혹시 질문 검색하실 분들을 위해서 남기자면...

저는 yukariko님이 처음에 언급했다는 방식대로 구현했는데,

시간은 412ms나 걸렸지만 맞았다고 떴습니다.

서버컴이 1년사이에 좋아져서 통과가 된걸까요??;

최대공약수 구해서 1부터 최대공약수까지 1씩 증가시켜가면 출력했거든요.

그리고 중간에 있는 2로 나눈다는 발상은 생각만해보고 짜진 않았는데, 그렇게 짜신 분도 있군요.

질문 검색했던 이유는 시간 짧게 걸리는 코드를 봐도 이해가 안가길래 뒤적뒤적하다가 여기서 appa님이 쓴 글 보고 잘 배워갑니다.