問題概要
正整数 $S, P$ が与えられる.$N + M = S, N \times M = P$ となる正整数 $N, M $ はあるか?
制約
- $1 \leq S, P \leq 10^{ 12 }$
解法
$N \times M = P$ は当然 $N \times M \leq P$ を imply します.更に,$N \times M \leq P$ から $\min( N, M ) \leq P$ が言えます*1.$\min( N, M )$ としてあり得る値をすべて試す処理は,(素因数分解や素数判定の容量で)$O( \sqrt P )$ 時間でできます.その値を $n$ としたとき,$n \times m = P$ となる $m $ は,存在すれば一意的にかつ $O( 1 )$ 時間で計算できます.その上で,$n + m = S$ であるかを判定することで,ある $n$ が feasible かどうかを判定できます.
コード
main = do [ s, p ] <- readIntegers putStrLn $ which "Yes" "No" $ not $ null $ do i <- takeWhile ( \i -> i * i <= p ) [ 1 .. ] guard $ p `mod` i == 0 let j = p `div` i; guard $ i + j == s return ()
*1:そうでないと仮定すると $N \times M > P$ になってしまいます