解いた問題のソースコードと解説など。


包除原理

POJ 2773 Happy 2006

問題 自然数m, Kが与えられる。mと互いに素なK番目の自然数を返せ。 やりかた 逐一調べると当然間に合わない。ここは二分探索+包除原理。まず二分探索で解の候補を上げ、その解の候補に対して、それ以下の自然数でかつmと互いに素なものの個数を計算し、その…

POJ 2407 Relatives

問題 n(1自然数の個数を求めよ。 やりかた 包除原理。 nの素因数p[]を求めておく。するとnと互いに素でないn未満の自然数の数は、をn未満のp[i]の倍数の集合とするとで求めることができる。これは包除原理をもとにすぐ計算できる。(Kはnの素因数の個数)以下…

SRM 477 Div2 Hard CarelessSecretary

問題 カードがN枚あり、各カードはそれぞれの袋に入っている。このカードをシャッフルして袋に入れなおし、この内K枚を取り出したときにK枚全てがもともとの袋にはいっていたものではなかった。このようなシャッフルの数はいくらか? やりかた いくつかの解…

SRM 491 Div2 Hard BottlesOnShelf

問題 http://community.topcoder.com/stat?c=problem_statement&pm=110081〜Nまでの間でleft[i]〜right[i]の間の数字の内、damage[i]で割り切れる数字を消去する。全部で消去される数はいくつか? やりかた 包除原理。まずは1~Nの整数に中でdamage中の少な…

罪を憎んで人は憎まずにセクシー