エラトステネスの篩
調和級数的計算量
- エラトステネスの篩がO(NlogN)で計算できるというような計算量の考え方を調和級数的計算量みたいに表現したりもする
- つまるところは「rep(i,1,N) for(j=i;j<=N;j+=i) というループ構造はO(NlogN)で行えるという所を応用して問題を解く」
http://yukicoder.me/problems/no/428
D = 0.123456789101112…
小数点以下が1から100まで順番に現れる小数Dがある。
これをN倍したものを出力せよ
1 <= N <= 100
http://yukicoder.me/problems/no/429
N個のコップがあり、K回2つのコップを入れ替える作業を行うがが、
X回目の作業で入れ替えたコップの位置だけ分からないので、答えよ。
入れ替え作業の流れは以下の通り。
2 <= N <= 10^5
1 <= K <= 10^5
http://yukicoder.me/problems/no/430
文字列Sがある。
M個の文字列C[i]がある。
文字列Sの部分文字列としてC[i]が何通りあるかをM個の文字列全て調べて、その総和を答える。
1 <= |S| <= 5*10^4
1 <= M <= 5 * 10^3
1 <= |C[i]| <= 10
1~Nの番号がついているグラフがある。
ここでM組のa[i]とb[i]が与えられる。
「XからYへの辺がある」⇔「Xがa[i]の倍数かつYがb[i]の倍数」で辺がある。
このとき、始点Sから始点Tまでの最短距離は?
もし到達不可能なら-1
2 <= N <= 10^9
1 <= M <= 10^3