【問題集】整数変数の式で表された条件を扱う探索
文字を固定したり、数式処理したりなど、総合力が問われる問題！ 問題へのリンク 問題概要 正の整数 が与えられる。非負整数 をすべて考えたときの、 の最小値を求めよ。 制約 まず、問題の理解 数学に慣れていないと、何がしたいのかわかりづらいと感じるか…
整数の入門にいい感じの問題！ 問題へのリンク 問題概要 正の整数 と非負整数 が与えられる。次の条件を満たす正の整数 の個数を求めよ。 を で割った余りが である 制約 解法 を で割ったときの商を とおくと、 と表せる。これを式変形すると となる。この…
これ、一見すると の計算量が必要に思えてしまうね！ 問題へのリンク 問題概要 正の整数 が与えられる。 かつ であるような正の整数の組 の個数を求めよ。 制約 の範囲を絞る 約数列挙アルゴリズムなどでもお馴染みの、大小関係から整数の範囲を絞って探索す…
なんかユーザー解説の数がすごいことになっててビビる！ 問題へのリンク editorials 問題概要 以下の正の整数 の組であって、 が平方数であるようなものの個数を求めよ。 制約 考えたこと この手の問題では「ある変数を固定して考える」という常套手段がある…
これも最近よく見る「整数の式で表された条件を扱う探索問題」の一味ですね！ 問題へのリンク 問題概要 整数 が与えられる。 正の整数 の組であって、 を満たすものの個数を求めよ。 制約 考えたこと もし計算時間をまったく気にしなくてよいならば、次のよ…
「ある量を固定して考えるとよい」「 まで調べればよい」という 2 つの典型を組み合わせて解ける問題ですね！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上の整数のうち、 以上 以下の 2 つの整数 の積 として書ける最小の整数を求めよ。 そのよう…
これ系は好き！ これに近いのを ABC-D で最近よく見かける気がする。 問題へのリンク 問題概要 整数 が与えられる。 3 つの整数の組 であって、 がすべて 以下であるようなものの個数を 998244353 で割ったあまりを求めよ。 ケース与えられる。 制約 考えた…
ほどよい全探索問題！ 約数列挙のアルゴリズムなどをちゃんと理解していれば解ける！ 問題へのリンク 問題概要 以下の正整数のうち、 なる素数 を用いて と表せるものはいくつあるか？ 制約 前提知識 この問題を見てまったく見当もつかないという場合には、…
面白かった 問題へのリンク 問題概要 以下の素数のみを素因数に持つ正整数を -smooth number と呼ぶ。 整数 および 、100 以下の素数 が与えられるので、 以下の -smooth number の個数を求めよ。 制約 考えたこと コンテスト中には、愚直 DFS を頑張って通…
色々な考え方ができる楽しい問題ですね！ 3 通りの解法を自分なりに咀嚼して整理しました。 問題へのリンク 問題概要 2 以上の整数 が与えられる。 が の倍数となるような最小の整数 を求めよ。 制約 考えること：まずは素因数分解 この問題のように、「倍数…
緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね！ 問題へのリンク 前提知識 エラトステネスのふるい 二分探索 問題概要 素数 を用いて と表される数を「250 に似た数」であると言います。 整数 が与えられますので、 以上 以下の「250…
前回の ABC に続いて、D 問題が数学っぽい。でも実際には今回は探索問題ですね。 問題へのリンク 問題概要 非負整数 を用いて と表せる整数 を「特別数」と呼ぶことにします。 非負整数 が与えられますので、 以上である最小の「特別数」を求めてください。 …
約数系包除原理の教育的問題 問題へのリンク 問題概要 整数 が与えられるので、以下の条件を満たす整数 の組の個数を求めてください。 としたとき、, , 制約 解法 (1)：約数系包除 まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を…
むずかしかった！！！ でも、約数列挙でありがちな「 まで試せば良い」という考え方がちゃんと理解できているかを問う良問だった！！ 問題へのリンク 問題概要 整数 が与えられる。 1 以上 以下の整数のうち、 2 以上の整数 を用いて と表せないものはいくつ…
これ FFT を使えば でもできるね。実際は で間に合う。 ジャッジページ 問題文 問題概要 正の素数 と、正の整数 が与えられる。 は 以上 以下の整数 を満たすような の組の個数を求めよ。 制約 は素数 考えたこと まずは次のように集計処理をしよう。このよ…
教育的な約数列挙問題！！ 問題へのリンク 問題概要 2 つの正の整数 が与えられます。 を満たす正の整数 が存在するかどうかを判定せよ。 制約 考えたこと として、 の約数のみを考えれば OK。そして を決めると は と決まる。 となることがあるかどうかを判…
エラトステネスの篩の練習問題に良さそう 問題へのリンク 問題概要 以上 以下の素数の組 であって、 を満たすものの個数を求めよ。 制約 考えたこと のときは明らかにダメ。 また、偶数かつ素数である整数は 2 のみであることに注意する。 がともに奇数とす…
ごとに考えるのではなく、集計する考え方をするのがポイント！！！ 問題へのリンク 問題概要 正の整数 が与えられる。各 に対して、 は正の整数 を満たすような の組の個数を求めよ。 制約 考えたこと 最初に特定の整数 に対して は正の整数 を満たす の個数…
完全に約数列挙！！！！！ 問題へのリンク 問題概要 正の整数 が与えられる。 の正の約数をすべて出力せよ。 制約 考えたこと 約数列挙問題そのものだった！！！！！ まったくそのまんまなものを次の記事の「3. 約数列挙」のところで書いた！ qiita.com 計算…
中国剰余定理使う問題楽しいよね！ 問題へのリンク 問題概要 正の整数 が与えられる。以下の条件を満たす最小の正の整数 を求めよ。 が の倍数である 制約 考えたこと まず、 なので、問題の条件は次と同値になる。 が の倍数である ここで改めて を で置き…
でもできる！ 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような正の整数 の組の個数を求めよ。 制約 考えたこと こういう整数問題は、実のところ本当に整数論的考察を必要とするパターンは少なくて、大抵は探索ベースの解法が有効になる！！…
一瞬ヤバそうに見えるけど、落ち着いて考えると、 くらいまで調べればいいという 問題へのリンク 問題概要 正の整数 が与えられるので、 を満たす整数 を一つ求めよ。 制約 考えたこと こういうの、基本的には全探索。でも という制約を見ると、 あたりまで…
約数列挙！！！ 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような正の整数 の組をすべて考えたときの、 の最小値を求めよ。 制約 考えたこと これはまさに約数列挙の問題！！！ 以下の記事の「3. 約数列挙」のところで、本質的に同じ問題の…
E8君問題集の第2問 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のうち、約数の個数がちょうど 8 個あるものが何個あるかを求めよ。 制約 考えたこと 単純に 1 から までの整数それぞれについて、 約数をすべて求めて それが 8 個かど…
「〜の最小値を求めてください」「ただし 1000000007 で割ったあまりで」 ...この設定の歪さを見ると、不思議な気持ちになる 問題へのリンク 問題概要 個の正の整数 が与えられる。 以下の条件を満たす正の整数列 をすべて考えたときの、 の最小値を求めよ (…
整数に関する問題でまずは直面する典型的な事柄を学べる教育的問題！！ 例えば整数 が素数かどうかを判定するのは、実は から まで順に試し割りすればよいという話など。 ただ、現代の ABC なら灰色 diff になりそうである。 問題へのリンク 問題概要 正の整…
代表的な全探索問題！ 問題へのリンク 問題概要 2 つの整数 が与えられます。 3 つの 以上 以下の整数 の組であって、 を満たすものが何通りあるか求めよ。 制約 全探索 一目見てすごく数学色強そうで怖そうなのだけど、とりあえず答えを出すコードを求める…
editorial は「75」という整数の特徴をフル活用している。 そして 75 という整数の特徴を活用しない DP による方法もあると説いている。 ここでは 75 という整数の特徴も活用せず、DP もしない (といっても DP への改良は容易) 愚直な全探索でも通った。 問…
素因数分解 & 重複組合せ を勉強できる、すごく教育的問題だった！！！ 問題へのリンク 問題概要 整数 が与えられる。 を満たす整数の組 () が何通りあるか、1000000007 で割った余りで求めよ。 制約 解法 素因数分解っぽいテーマの問題。こういうのは「まず…
問題概要 2 個の正整数 A,B が与えられる。 A! の約数である B! の倍数である ような正整数の個数を 1,000,000,007 で割った余りを求めよ。 制約 解法 求める正整数は とおける。これが の約数であることから、 | であることが言える。よって、 の約数の個数…
