이 코드는 for문에서 막히는 게 맞습니다. N이 최대 50000이고, a//d와 b//d가 최대 50000이므로 len(dba)와 len(dbb) 둘 다 최대 50000인데, 위 코드는 따지고보면 이 세 수에 대해서 전부 루프를 돌리고 있기 때문에 50000^3 ~ 10^17번의 루프를 돌리려 합니다. 당연히 시간초과가 납니다.

이걸 해결하는 게 이 문제의 핵심으로 보여서, 어떻게 수정하면 좋겠다 조언드리는 건 문제를 직접 풀어드리는 거나 다름이 없어 곤란합니다. 다만 단순히 루프를 돌려서 답에 해당하는 경우를 일일이 세는 건 무리라는 건 말씀드릴 수 있습니다.

감사합니다 조금 더 공부해보겠습니다!

이 문제는 수학을 활용해서 코드를 최적해야 하는 문제로, 난이도가 많이 높습니다.

곱함수(multiplicative functions)와 관련된 정수론적 지식을 배우신 게 아니라면 이 문제를 도전하는 건 추천드리지 않으며, 정수론 문제가 어느정도 익숙한 상태가 아니라면 이 문제를 위해 관련 내용을 지금 시점에서 굳이 공부하는 건 과하다고 생각합니다.

아..

감사합니다.

사실 쉬워보여서 시도해봤는데, 코딩실력보단 다른 정수론적 지식이 필요한건가 보네요

더 이상 시도는 안하도록 하겠습니다.. ㅎㅎ