1091 Tmutarakan exams

問題:

S以下の数から, K個を選んでその最大公約数が1でないものを求めたい. このような組み合わせの個数を求める問題.

基本解法:

ある数xの倍数の中から選べば最大公約数は1とはならない. サンプルに含まれる, S=10, K=3だとすると,

  1. x=2の場合: 2,4,6,8,10 より, 5C3 = 10
  2. x=3の場合: 3,6,9 より, 3C3 = 1 合計で, 11となる.

解法:

難しいのは, xが素数でない場合であろう.

  1. x=4=2*2の場合: その組み合わせはすでにx=2の場合に数えられている.
  2. x=6=2*3の場合: その組み合わせはx=2とx=3の場合で数えられている. したがって, x=6の場合はの数を引かなければならない.

さらに, x=30=2*3*5の場合: 引きすぎなので, これは足す.

これをうまくまとめれば, とても簡単な問題になります.

プログラム

松崎 file1091.matsuzaki.cpp


添付ファイル: file1091.matsuzaki.cpp 493件 [詳細]

Last-modified: 2009-11-06 (金) 13:25:51 (3426d)