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の場合: 引きすぎなので, これは足す.

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

プログラム †

松崎 1091.matsuzaki.cpp