[CSA] Round #2 Online Gcd

Online Gcd

https://csacademy.com/contest/beta-round-2/task/online_gcd/statement/

最大公約数の問題ですが、Javaで解くと入出力がボトルネックになると思います。なので、自作の標準入出力のライブラリを用意する必要があります。

考え方

まず初めに \( N \) 個の整数の配列を \( a \) とし、この配列の最大公約数を \( g \) とします。そのあとの \( M \) 回の操作は、整数 \( i, k \) が与えられ、配列の要素を

\[ a_i = \dfrac{a_i}{k} \]

として更新します。この時の配列 \( a \) の最大公約数を解答として出力します。

更新後の配列の最大公約数は、

\[ g = gcd(g, a_i)\]

となります。

ソースコード

標準入出力は、

https://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4

で紹介されているものを利用しました。

感想

JavaのScannerは遅いので、入力が多い問題は自前のライブラリを使う必要があります。このライブラリを自分で用意するのは大変なので、他の人の解答例を参考にして作るか、紹介されているものを利用したいと思います。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする