数学(整数問題)
演算子「%」を上手に使う系の数学問題。 問題へのリンク 問題概要 種類のゴミがある。ゴミ は、 で割って 余る日に捨てることができる。 次の 個のクエリに答えよ。 【クエリ】 ゴミ を、 日目以降に捨てたい。最短で捨てることのできる日を答えよ。 制約 考…
探索アプローチでも解けるし、整数論的考察で解くこともできる。 問題へのリンク 問題概要 の倍数であって正の整数であるものをいくつか用意する。 その総和を で割った余りが となることはありうるか？ 制約 考えたこと まず、「いくつかの正の の倍数を足…
mod 1000000007 をする問題。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 正の整数 が与えられる。 を 1000000007 で割った余りを求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; // a^n mod m template<class T> T mod_pow(T a, T n, T m) { T </class></bits/stdc++.h>…
mod の練習。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 最初、黒板に 0 という数が書かれている。以下の 回の操作を実行せよ。各操作では文字 と数 が与えられる。 = '+' のとき：黒板に書かれた数を、 を足した数に書き直す = '-' のとき…
最大公約数。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 2 つの正の整数 の最大公約数を求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; long long GCD(long long x, long long y) { if (y == 0) return x; else return GCD(y, x % y)</bits/stdc++.h>…
コンテスト中最初に挑んだが解けず、その後も結局解けなかった。gcd convolution を思い出せなかった。 問題へのリンク 問題概要 長さ の正の整数からなる数列 、 が与えられる。これらの数列に対して 個のクエリが与えられる。 【クエリ】 正の整数 が与え…
素数判定。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 個の整数 がそれぞれ素数であるかどうかを判定せよ。 制約 コード #include <bits/stdc++.h> using namespace std; bool is_prime(int N) { if (N <= 1) return false; for (int x = 2; x * x <= N; x+</bits/stdc++.h>…
mod を練習できる問題！ 問題へのリンク 問題概要 正の整数 が与えられる。 を 1000000007 で割った余りを求めよ。 考えたこと まず「1000000007 で割った余り」といったものを考えるための、基本的な知見を次の記事にまとめた。 qiita.com 結論として、 を …
三進法をテーマにした問題！ 問題へのリンク 問題概要 正の整数 が与えられる。以下の条件を全て満たす正の整数 と非負整数列 を 1 つ求めよ。 制約 考えたこと 問題文が一見わかりにくいかもしれない。こういうときは具体的にやってみよう。 たとえば のと…
問題文の理解が大変かもしれない 問題へのリンク 問題概要（意訳） 2 つの正の整数 を次のように 回更新していく。最初、 である。 回目の更新では 2 つの互いに素な正の整数 が与えられるので、 を満たすような 2 つの正の整数 を 1 つ求めて、 をそれぞれ …
で場合分けする系！ 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす最小の整数 （）を求めよ。(存在しない場合は -1。） 【条件】 を 進法表記したときの桁の和が である 制約 考えたこと が小さい範囲は愚直に調べればよさそうだ。 があ…
偶数と奇数に関する理解も問われる問題。 問題へのリンク 問題概要 2 つの整数 が与えられる。 「 を並び替えると等差数列をなす」 という条件をみたすような整数 が何通りあるか求めよ。 制約 解法 (1)：数学的に解く まず、 の大小関係で場合分けして考え…
問題の条件をいかにうまく言い換えるか！ 問題へのリンク 問題概要 2 つの整数 が与えられる（）。 を小数点第四位を四捨五入して、小数点第三位まで表した結果を求めよ。 考えたこと を整数型ではなく、浮動小数点型として受け取って、B / A を計算して小数…
規則性を発見しよう！ この規則は今後セグメントツリーなどを学ぶときにも活用する！ 問題へのリンク 問題概要 次の図において、 番目の頂点と 番目の頂点がつながっているかを判定せよ。 考えたこと 図を見ると、次の規則があることがわかる。 番号が であ…
16進法に関する問題！ 問題へのリンク 問題概要 0 以上 255 以下の整数 が与えられる。 の 16 進法表記を求めよ。 考えたこと 16 進法について知識がなかったら、たとえば次のような記事で勉強するとよさそう！ zenn.dev であり、今回与えられる整数 は 255 …
落ち着いて整理していこう！ 問題へのリンク 問題概要 以上の最小の 4 で割って 2 余る整数を求めよ。 制約 考えたこと を 4 で割った余りによって場合分けして考えよう。 が 4 で割り切れるとき：2 足すことで「4 で割って 2 余る整数」になるので、 が答え…
整数として扱っても解けるけど、文字列として処理するのが楽だと思う！ 問題へのリンク 問題概要 100 以上の 3 桁の整数 が与えられるので、 の下二桁を出力せよ。 解法 3 桁の整数値を文字列 N として入力を受け取ろう。たとえば、459 という整数は、"459" …
十の位と一の位から、整数値を求めよう。 問題へのリンク 問題概要 2 つの整数 が与えられる。 十の位が 、一の位が であるような 2 桁の正の整数を求めよ。 制約 考えたこと このような問いは、中学数学でよく学ぶ。 一般に、十の位が 、一の位が であるよ…
包除原理した！ 問題へのリンク 問題概要 1 以上 以下の正整数 であって、ある正整数 と 2 以上の正整数 を用いて と表現できるものはいくつありますか？ 制約 考えたこと まず考えたのは、 は素数のみ考えれば良いということだった。たとえば、 というよう…
全探索でやってしまうのが楽だと思われる。 問題へのリンク 問題概要 正の整数 が与えられる。 をともに割り切る整数のうち、 番目に大きいものを求めよ。 制約 をともに割り切る整数のうち、 番目に大きいものが存在する 考えたこと 全探索で解いてしまうの…
包除原理の基本！ 問題へのリンク 問題概要 1 以上 以下の整数のうち、 のいずれかで割り切れるものの個数を求めよ。 制約 考えたこと 包除原理の超典型問題。たとえば のときは、次のように考えればよい。 (V[0] で割り切れる個数) + (V[1] で割り切れる個…
面白かった！ 問題へのリンク 問題概要 整数 が与えられる。 整数 の十進法表記を 個 concat してできる整数を 998244353 で割った余りを求めよ。 制約 考えたこと まず、整数 が 桁だとしよう！ このとき、求めたい値は次のように表現できる。 よって、 と…
mod 998244353 の練習！ 問題へのリンク 問題概要 非負整数 が与えられる。 を 998244353 で割った余りを求めよ。 制約 考えたこと 「足し算・引き算・かけ算」をした計算結果を 998244353 で割った余りを求める方法論については、次の記事に詳しく書いた。 …
素因数分解を上手に活用しよう！ 問題へのリンク 問題概要 正の整数 が与えられる。 の正の約数の個数を 1000000007 で割った余りを求めよ。 制約 考えたこと 「約数の個数」をまともに考察する場合には、素因数分解が役にたつことが多い。一般に正の整数 が…
制約が と大きいので、ちゃんと整数論的処理をしないといけない！ 問題へのリンク 問題概要 以上 以下の整数のうち、 の倍数は何個あるか？ 制約 考えたこと 制約が と極めて大きいので探索手法で解くことは難しい。数学的に求めることを考える。 まず、「 …
これ結構難しい！ 数式を丁寧に立てよう。 問題へのリンク 問題概要 箱に水色のボールが 個入っている。 「箱に 個の水色のボールと、 個の赤色のボールを入れる」という操作を繰り返すことで、赤色のボールの個数が水色のボールの個数の 倍以上となるように…
「十進法 → 二進法」変換。これも鉄則本公式解説とは異なる方法でやってみよう。 問題へのリンク editorial 問題概要 二進法で表記された整数 が与えられる。 整数 の十進法表記を求めよ。 解法 たとえば、二進法で表された整数 1101 は、十進法では、次のよ…
ここでは鉄則本に乗っているのとは異なる方法でやってみよう！ 問題へのリンク 問題概要 整数 が与えられる。 を二進法表記したものについて、先頭を 0 埋めすることで 10 桁で答えよ。 解法：二進法とは 整数 を二進法で表したときの各桁の値が求められれば…
整数に対する for 文を用いての全探索です！ 問題へのリンク 問題概要 以上 以下の整数のうち、100 の約数であるものは存在するか、判定せよ。 解法 github.com コード #include <bits/stdc++.h> using namespace std; int main() { int A, B; cin >> A >> B; bool res = fa</bits/stdc++.h>…
慣れていないと少し難しいかもしれない。 問題へのリンク editorial 問題概要 今日は日曜日である。 今日の 日後が火曜日であるならば 1 を、そうでないならば 0 を出力せよ。 解法 日後が火曜日であるための条件を考えましょう。 「0 日後は日曜日」「1 日…
