oVeron

\(2xy + x + y = A\)라 하면, \(2A+1 = 2(2xy + x + y) + 1 = 4xy + 2x + 2y + 1 = (2x + 1)(2y+1)\)이다. \(x, y\)는 양수이기에 \(2x+1, 2y+1\)는 3 이상의 양수이고, 때문에 \(2A+1\)은 반드시 9 이상의 소수가 아닌 양수이다. 즉 \(2A+1\)에 대해 소수를 판별하면 문제를 해결할 수 있다. 단, 면적 \(A\)의 크기가 정수 최대 범위기에, \(O(sqrt(N))\) 소수판정법을 쓰면 TLE를 받는다. 때문에 \(O(log^3N)\) 소수 판정법인 밀러-라빈을 써야만 한다. 밀러-라빈을 쓸 때 지수로 들어가는 값이 정수 최대 범위이므로, long long이 아닌 unsigned long long을 써야 한다.소수를..

알고리즘/baekjoon 2024. 7. 21. 22:17