ABC112 Partition
所見
この問題のように式が与えられてそれを変形するだけで解けると余裕だが、AGC017Bみたいに条件を式にするフェーズがあるとそこで死亡することが多い?
紙を用意しような
(企業コン除く)400点埋まりました
400点終わりです https://t.co/ggRrzZ8q7j pic.twitter.com/jSU0S1PsUO
— AIRをプレイする (@ymduu) October 25, 2018
問題概要
N,Mが与えられる。 N個の数からなる和がMの数列において、数列の最大公約数の取りうる最大値を求めよ。
取った方針
最大公約数をqと置くと、a_1+...a_N=Mの左辺をqでくくることができる。
q(b_1+...+b_N)=M
両辺qで割って
b_1+...b_N=M/q
b_iは1以上なので、M/qがN以上になればよい。
Mの約数のうち、M/qがN以上になるものを計算して終了
正しい方針
同上
得られた知見
- 特になし
解くのに必要な要素
- 式変形
周辺調査によって得られた知見
特になし