【AtCoder】CADDi 2018 C問題 最大公約数(GCD)系の問題が出た時のポイントについて 【C#】

どうも数学的な処理をするのが苦手なようなので、下記問題を解いた時にポイントとなった箇所をまとめます。

atcoder.jp

問題の概要

• N個の1以上の整数が与えられる
• 与えられた整数の値はわからない
• P = a1* a2 * ,,, * aN となることがわかっている
• a1,,,aNの最大公約数として、最も大きいものを求めよ

公式説明動画

まずは、これを見てください。

www.youtube.com

説明動画での処理の流れまとめ

ここで、解説にあった処理のプロセスをまとめます。

1. gcd(a1,,,aN)をgと置く
2. 1より、a1,,,aNの各値はgの倍数であることがわかる
3. 2より、Pがgⁿの倍数となることがわかる
4. つまり、3で書いた条件を満たすようなgの値をみつける
5. P を X に置き換え、素因数分解する
6. X = P1^e1 * P2^e2...*Pk^ek と置き換える
7. g^N が上記の約数になっていてほしい
8. gは X にはないような素因子はでてこないので、 g = P1^f1 * P2^f2...*Pk^fk とかける(かりにXにあってgにない素因子があっても、fi を 1 にすればよい)
9. g^N なので、fi * N <= ei を満たすfiをもとめる
10. fi = N/ei となる

fiを求めたら計算してgを出して完了

自分で考察する時のポイント

5.までは考察できるが、それ以降が難しい。例えば、6.-10. の流れはコンテスト中に思いつくか微妙。

思いつくために、GCD問題のときは下記に注意してみたい

• GCDを求めた時、GCDを求める対象となった各要素はGCDの倍数となる(3.)

• 各要素がN個あった時、N個から求めたGCDのN乗は各要素をかけ合わせた値の約数となる(7.)

• 各要素をかけ合わせた値を素因数分解したとき、GCDの値は同じ素因子を使用して表現することが可能(8.)

上記の性質を抑えておけば、同じような問題が出た時になにかしらの取っ掛かりになるのではないかと思う。

感想

茶色問題はもっと安定してとけるようになりたし。。