Namaran

Code daily. Without assist.

2026-11-11

Coprime.hs

pairwiseCoprime :: [Int] -> Bool

整数のリスト xs から異なる位置の2つの要素をどう選んでも、その最大公約数が1なら True、そうでなければ False を返す pairwiseCoprime を書いてください。要素はすべて1以上です。要素が1つ以下のときは、選べる組が無いので True です。

入力例 1

pairwiseCoprime [3, 5, 7]

出力例 1

True

入力例 2

pairwiseCoprime [4, 9, 10]

出力例 2

False

入力例 3

pairwiseCoprime []

出力例 3

True
Reference

Reference

import Data.List (tails)

pairwiseCoprime :: [Int] -> Bool
pairwiseCoprime xs = and [gcd a b == 1 | (a : bs) <- tails xs, b <- bs]

tails xs は xs の後ろの部分を長い順に並べたリストで、[4, 9, 10] なら [[4, 9, 10], [9, 10], [10], []] です。内包表記で各要素を (a : bs) と受けると、a とそれより後ろの要素 b の組がちょうど1回ずつ作られます。すべての組で gcd a b == 1 なら and が True を返します。これは参考実装で、唯一の正解ではありません。

入力例2で、隣り合う 4 と 9、9 と 10 の最大公約数はどちらも1ですが、離れた 4 と 10 は2を共有しています。隣どうしだけを調べると、この組を見落として True を返してしまいます。空リストと1要素のリストでは組が1つも作られず、and [] は True なので、境界の場合を別に書く必要はありません。最後の [] はパターン (a : bs) に一致せず、内包表記の中では一致しない要素が読み飛ばされます。