그 대충 풀이는 하겠는데 구현이 자꾸 실패해서 못풀고 있긴한데

2xy+x+y=k니까

(2x+1)y=(k-x) 즉

k-x가 2x+1 로 나누어떨어지냐 마냐의 문제인듯 합니다. \

2xy+x+y를 인수분해할 수 있는 형태로 변형해 보세요.

조금만 더 힌트 주실 수 있나요?

인수분해를 하면 딱 유레카하고! 알 수 있나요? 아니면 거기서 뭘 더 해야할까요?

인수분해를 대충 하긴했는데, 이걸 어떻게 활용할 수 있을지 감이 안오네요.

지난번에 N제곱 계산문제에 대해서 https://www.acmicpc.net/board/... 라고 답변을 해주셨었는데요.

그때도 어떻게 해야할지 하나도 모르겠고, 감이 아예 안잡히더라구요.

제가 아마도 jh님이 의도하신대로 인수분해를 해서 적절한 식을 구했는데요.

이걸 이용하려고 해도,

제가 그 전에 시도했던 방법

https://www.acmicpc.net/source...

이것의 시간복잡도를 전혀 벗어나지 못하는 방법밖에 생각이 안나는데 혹시 더 생각해야 될 것이 있을까요?

제가 의도한 식이 맞다면 "???가 소수"임을 판별하는 문제가 됩니다. 밀러-라빈 소수판별법을 찾아보세요.

네 그런데 그수가 커서 시간복잡도 내에 안될거 같았거든요.

특별한 소수판별법을 이용해야 풀리는 문제군요. 답변 감사합니다 !

제 원래 코드는 2^15이하의 모든 소수를 뽑아서 배열에 담아놓고 

탐색하는 방법이라서 3510 * n의 수행시간이 필요했는데, 소수판별 알고리즘을 이용하면 되겠네요.

답변 감사합니다.

저도 시간 복잡도가 문제였는데 정말 감사합니다

덕분에 해결했습니다. 진심으로 감사드립니다.

아마 제가 풀어본 문제중에 제일 어려운 문제인것 같군요.

소수판별 알고리즘을 사용해도 시간 엄청 타이트하네요.

도중에 구현 다해도 시간초과 나길래 책상에 엎드려 울고싶었는데, 

보니까 제가 사용하는 지수승 알고리즘이 (log2n)^2 였네요. ㅠㅠ 

아무튼 잡소리가 길었습니다. 감사합니다.