Official
A - Next TTPC 2 Editorial by mencotton
要約
\(\gcd(X-2015, Y-2015)\) の約数を昇順に出力すると AC します。
TTPC は \(2015 + A \times n\) (\(n\) は非負整数) と表すことができる年に開催されます。よって、\(X\) 年にも \(Y\) 年にも開催されるには、
- \(X=2015+A \times n_1\) となる非負整数 \(n_1\) が存在する
- \(Y=2015+A \times n_2\) となる非負整数 \(n_2\) が存在する
の両方を満たすことが 必要十分 です。これを変形すると、 「\(A\) が \(X-2015\) を割り切り、かつ \(A\) が \(Y-2015\) も割り切る」という条件になります。すなわち、\(A\) は \(X-2015\) と \( Y-2015\) との 公約数 です。 自然数 \(N\) の約数列挙は \(O(\sqrt N)\) で可能である ため、時間制限に間に合います。
また、最大公約数を求めその約数を列挙することでも公約数を列挙できます。最大公約数は ユークリッドの互除法 を実装することで計算できますし、言語によっては最大公約数を求める関数が gcd などの名称で存在し、そのまま使える場合もあります。
実装例1 (C++) (約数の共通部分)
実装例2 (C++) (最大公約数の約数)
posted:
last update: