差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:contest_history:atcoder:2020:0110_abc150 [2020/01/12] – [解法] ikatakosprogramming_algorithm:contest_history:atcoder:2020:0110_abc150 [2020/01/12] ikatakos
行 1: 行 1:
-======AtCoder Beginner Contest 150======+======AtCoder Beginner Contest 150 D~F問題メモ======
  
 [[https://atcoder.jp/contests/abc150|AtCoder Beginner Contest 150]] [[https://atcoder.jp/contests/abc150|AtCoder Beginner Contest 150]]
 +
 +  * 解説放送: [[https://www.youtube.com/watch?v=9MphwmIsO7Q|AtCoder Beginner Contest 150 - YouTube]]
  
 ===== D - Semi Common Multiple ===== ===== D - Semi Common Multiple =====
行 32: 行 34:
 2数 n,m の最小公倍数は、最大公約数を g として nmg で求められる。3数以上なら、これを繰り返し適用しつづければよい。 2数 n,m の最小公倍数は、最大公約数を g として nmg で求められる。3数以上なら、これを繰り返し適用しつづければよい。
  
-ただし bi が互いに素だと繰り返している内にとてつもなく大きくなってしまう。途中で M 以上になった時点で M 以下の半公倍数は不可能なので、0を出力して即終了する。+ただし bi が互いに素だと、最小公倍数は繰り返している内にとてつもなく大きくなってしまう。途中で M 以上になった時点で M 以下の半公倍数は不可能なので、0を出力して即終了する。
  
 <sxh python> <sxh python>
行 115: 行 117:
 しかし、このままでは1つの i を求める内部でさらに のループがあるため O(N2) となってしまう。 しかし、このままでは1つの i を求める内部でさらに のループがあるため O(N2) となってしまう。
  
-ここで、二項係数の総和の公式より、$\displaystyle \sum_{r=0}^{n}{{}_nC_r \times (r+1)}=2^{n-1} \times (n+2)$ となることを利用できる。+ここで、二項係数の総和の公式より、r=0nnCr(r+1)=2n1(n+2) となることを利用できる。
  
   * [[https://www.wolframalpha.com/input/?i=sum+ncr%28n%2C+k%29+*+%28k%2B1%29%2C+k%3D0+to+n&lang=ja|sum ncr(n, k) * (k+1), k=0 to n - Wolfram|Alpha]]   * [[https://www.wolframalpha.com/input/?i=sum+ncr%28n%2C+k%29+*+%28k%2B1%29%2C+k%3D0+to+n&lang=ja|sum ncr(n, k) * (k+1), k=0 to n - Wolfram|Alpha]]
programming_algorithm/contest_history/atcoder/2020/0110_abc150.txt · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0