torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Regular Contest 108, A : Sum and Product

問題概要

 正整数 $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$ になってしまいます