差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン最新のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2020:0110_abc150 [2020/01/12] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0110_abc150 [2020/01/12] – [解法] ikatakos | ||
|---|---|---|---|
| 行 2: | 行 2: | ||
| [[https:// | [[https:// | ||
| + | |||
| + | * 解説放送: | ||
| ===== D - Semi Common Multiple ===== | ===== D - Semi Common Multiple ===== | ||
| 行 32: | 行 34: | ||
| 2数 $n,m$ の最小公倍数は、最大公約数を $g$ として $\frac{nm}{g}$ で求められる。3数以上なら、これを繰り返し適用しつづければよい。 | 2数 $n,m$ の最小公倍数は、最大公約数を $g$ として $\frac{nm}{g}$ で求められる。3数以上なら、これを繰り返し適用しつづければよい。 | ||
| - | ただし $b_i$ が互いに素だと繰り返している内にとてつもなく大きくなってしまう。途中で $M$ 以上になった時点で $M$ 以下の半公倍数は不可能なので、0を出力して即終了する。 | + | ただし $b_i$ が互いに素だと、最小公倍数は繰り返している内にとてつもなく大きくなってしまう。途中で $M$ 以上になった時点で $M$ 以下の半公倍数は不可能なので、0を出力して即終了する。 |
| <sxh python> | <sxh python> | ||
| 行 115: | 行 117: | ||
| しかし、このままでは1つの $i$ を求める内部でさらに $\sum$ のループがあるため $O(N^2)$ となってしまう。 | しかし、このままでは1つの $i$ を求める内部でさらに $\sum$ のループがあるため $O(N^2)$ となってしまう。 | ||
| - | ここで、二項係数の総和の公式より、$\displaystyle \sum_{r=0}^{n}{{}_nC_r | + | ここで、二項係数の総和の公式より、$\displaystyle \sum_{r=0}^{n}{{}_nC_r(r+1)}=2^{n-1}(n+2)$ となることを利用できる。 |
| * [[https:// | * [[https:// | ||
