ICPC 2025 예선 I번 풀이

문제:
정수 -10^7 <= k <=10^7 이 주어진다.

x^2 + px+kp의 해가 모두 정수가 되도록 하는 
서로 다른 p의 개수와 합을 구하시오.



한글 문제인데 바로 안 보여서 오래 고민했다..
일반성을 잃지 않고 두 근을 a<=b라고 해보자.

 

-p=a+b
kp=ab이다.
그런데, -p=a+b<=2*b이다.

따라서 -k=kp/(-p) =ab/(a+b)>=ab/2b=a/2

|a|<=2k이므로 이를 이용하여 작은 근을 brute force 하면 된다.
a가 고정되면 p는 결정적으로 정해진다.