けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

エラトステネスの篩

TopCoder SRM 400 D1E StrongPrimePower

詰めるの大変だった。こういうの 240pt で通せる人ってどうなってるの!? 問題へのリンク 問題概要 2 以上の整数 が与えられる。 が狭義の素数べき (素数 と 2 以上の整数 を用いて と書ける数) であるかどうかを判定し、素数べきの場合には の値を求めよ。…

yukicoder No.886 Direct

添字 GCD 畳み込みの練習に 問題へのリンク 問題概要 の格子点上の二点対であって、その二点を結ぶ線分上に格子点をもたないものが何個あるかを数え上げよ。(1000000007 で割ったあまりで) 制約 解法 1:添字 GCD 畳み込み この問題は、線分として 軸や 軸に…

Tenka1 2019 E - Polynomial Divisors (800 点)

最大公約数を求めるときに abs つけてれば通ってた。。。 なにこれ悔しすぎる。。。 問題へのリンク 問題概要 次の整数係数多項式 が与えられる。任意の整数 に対して が で割り切れるような素数 をすべて求めよ。 制約 考えたこと めっちゃ好き!!!!!!…

AtCoder ABC 084 D - 2017-like Number (400 点)

累積和を用いる典型な感じ! atcoder.jp ここで解説を行った: qiita.com

Codeforces #548 Div. 2 D - Steps to One (R2300)

これだった!!! drken1215.hatenablog.com もちろん高速ゼータ変換はいらなくて、愚直な包除原理で間に合う。 問題概要 整数 が与えられる。空の vector があって 以上 以下の整数の中から一様ランダムに 1 つ選び、 それを vector に push する このとき …

Codeforces 511 DIV1 A - Enlarge GCD

大昔 osa_k 法と呼ばれていたやつ。 問題へのリンク 問題概要 個の整数 が与えられ、 をこれらの最大公約数とする。 今、 個の整数から何個かを取り除いて、その最大公約数が より大きくなるようにしたい。取り除くべき最小個数を求めよ。ただし、どのように…

AtCoder AGC 027 D - Modulo Matrix (1100 点)

悔しい... 問題へのリンク 問題概要 (AGC 027 D) 整数 が与えらる。以下の条件を満たすような 行列 a を 1 つ構築せよ: 各要素の値は 以上 以下 ある正の整数 が存在して、行列の上下左右に隣接する 2 数 をどこから取り出しても、max() を min() で割ったあ…

AOJ 1276 Prime Gap (AOJ-ICPC 200 点)

素数砂漠なん!!! 問題へのリンク 問題概要 整数 が与えられる。 を含む素数砂漠 (連続する合成数) の長さを求めよ。 すなわち、 以上の最小の素数と、 以下の最大の素数との差を求めよ。 制約 解法 エラトステネスの篩で予め 2000000 くらいまでの整数に…