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

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

整数問題

AtCoder AGC 001 B - Mysterious Light (500 点)

Euclid の互除法な操作過程をたっぷりと味わえる味わい深い問題。 問題へのリンク 問題概要 一辺の長さが の正三角形の図のような の地点からビームを発射する。このとき、既にビームが通ったところは新たに壁になる。ビームは必ず元の場所に戻ることが証明…

AOJ 2720 Identity Function (JAG 夏合宿 2015 day4-D) (600 点)

この問題の原案やってました!高校の頃、時刻表同好会の友達から 「f(n) = n15 を 15 で割った余りとすると任意の整数 n に対して f(f(n)) = n になるんだけど、これって暗号の危機じゃない?」 というメールを受け取って、あれこれ考えたことがキッカケにな…

AOJ 2932 約数ゲーム (RUPC 2019 day3-C)

B 問題が結構大変なのに比べて C 問題は毎度穏やかな感じ 問題へのリンク 問題概要 整数 が与えられる。これを使ってゲームをする。 の真の約数の中から整数を 1 つ宣言する、ただしこのとき既に宣言したことのある整数の約数になるものは宣言できない 宣言…

AtCoder ABC 121 D - XOR World (緑色, 400 点)

みんな早い...!!! 問題へのリンク 問題概要 2 つの整数 () が与えられる。 以上 以下のすべての整数の XOR 和を求めよ。 制約 「A 以上 B 以下」と、「XOR の引き算」とは まず「 以上 以下の値の総和を求めよ」という問題は、「 以下の値の総和を求めよ…

AOJ 3062 Product (RUPC 2019 day2-L)

本当に悔しい。BSGS に無限にこだわってしまった。なぜ方針転換を図れなかったのか。。。 そしてこの問題、本当に本当に整数論の魅力がたっぷり詰まった楽しい問題だった。作問してくれた会津大チームにすごく感謝!!!!!!!!!! 問題へのリンク 問題…

AtCoder ABC 118 C - Monsters Battle Royale (茶色, 300 点)

教育的!!! 問題へのリンク 問題概要 個の正の整数 が与えられる。今、以下の操作を好きな回数だけ行う。 個から 2 つの正の整数 () を選んで、 を で置き換える この操作を行うと、最終的には 個の と 1 個の正の整数が残る。残る整数の最小値を求めよ。 …

AtCoder AGC 010 D - Decrementing (橙色, 1000 点)

一目見て惹かれた。すごく面白かった。割と自然な考察の流れで解けた。 問題へのリンク 問題概要 個の正の整数からなる数列 が与えられる。先手と後手が交互に以下を繰り返す。先に操作を行えなくなった方が負けである。双方最善を尽くしたときにどちらが勝…

QUPC 2018 I - Buffalo

楽しいけど重くて、重いけど楽しい 問題へのリンク 問題概要 要素から成る数列 が与えられる。 個から 2 個選んでできる 通りのペア のうち、以下の条件を満たすものを数え上げよ。 容量が の容器を用意して、以下の操作によって水の量 を汲み取れる 操作 1:…

Codeforces AIM Tech Round (Div. 1 + Div. 2) 5 F. Make Symmetrical (R2900)

僕の以前書いた記事、共円がちょっと関係ある問題だ!!!!!!!!!!!!! ガウス整数!!!!!!!!!!!!!!!!!!! 問題へのリンク 問題概要 二次元平面に関する以下の 3 種類のクエリ ( 個) に答えよ 格子点 に石をおく 格子点 においてあ…

CADDi 2018 C - Product and GCD (茶色, 300 点)

好き 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような 個の正の整数 の組合せをすべて考えたとき、 の最大公約数として考えられる最大値を求めよ。 考えたこと を素因数分解して、各素因子たちを に振り分けることを考える。 このとき、各…

AtCoder ABC 112 D - Partition (緑色, 400 点)

すごく教育的ないい問題な感じ 問題へのリンク 問題概要 整数 , が与えられる。 を満たす正の整数列 をすべて考えたときの、 の最大公約数の最大値を求めよ。 制約 考えたこと 候補を一気に絞る まず の最大公約数が必ず の約数になることがわかる。まずはこ…

AtCoder AGC 028 A - Two Abbreviations (茶色, 300 点)

そろそろまた競プロやっていくぞー!!! 問題へのリンク 問題概要 長さ n の文字列 S と長さ m の文字列 T が与えられる。以下の条件を満たす文字列 X があるかどうか判定し、あるならば X の長さ L として考えられる最小値を求めよ。 (以下において、n' = …

AtCoder ARC 004 D - 表現の自由 (黄色)

これがインフレ!?ABC 110 D - Factorization に瓜二つ 問題へのリンク 問題概要 整数 を 個の整数の積として表す方法が何通りあるかを、1000000007 で割ったあまりを求めよ。 制約 考えたこと ほとんど、ABC 110 D - Factorization と一緒。 だが、マイナ…

AtCoder AGC 003 D - Anticube (橙色, 1100 点)

とくらちゃん・シンヤカトー・てんぷらたんたちと気合いで解いた。 問題へのリンク 問題概要 個の正の整数 が与えられる。この中から最大個数の要素を取り出して どの 2 つをとってもその積が立方数とはならない という条件を満たすようにせよ。 制約 解法 …

Codeforces Round #511 (Div. 1) A - Enlarge GCD (R1800)

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

AtCoder ABC 110 D - Factorization (青色, 400 点)

素因数分解 & 重複組合せ を勉強できる、すごく教育的問題だった!!! 問題へのリンク 問題概要 (ABC 110 D) 整数 が与えられる。 を満たす整数の組 () が何通りあるか、1000000007 で割った余りで求めよ。 制約 解法 素因数分解っぽいテーマの問題。こうい…

AtCoder AGC 027 D - Modulo Matrix (赤色, 1100 点)

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

AtCoder ARC 034 C - 約数かつ倍数 (水色)

問題概要 (ARC 034 C) 2 個の正整数 A,B が与えられる。 A! の約数であり、かつ B! の倍数でもあるような正整数の個数を 1,000,000,007 で割った余りを求めよ。 制約 1 <= B <= A <= 109 A - B <= 100 解法 求める正整数は とおける。これが の約数であるこ…

AtCoder ABC 109 C - Skip (茶色, 300 点)

一瞬「訪れる順番によって状況が変わらないか...」と不安になるかもな問題だけど、よく考えたら訪れる順番を考える必要もない。ソートしても OK だけどソートする必要はなかった。 問題へのリンク 問題概要 個の点が一直線上に並んでいて、各頂点の座標は で…

AtCoder ARC 060 F - 最良表現 (赤色, 900 点)

今回は Suffix Array でやってみたけど、ローリングハッシュとか、KMP とか、Z-Algorithm とか、色んな方法があるみたいなので追々やってみたい。 → やってみた (3/14) 問題へのリンク 問題概要 文字列 がよい文字列であるとは「いかなる文字列 および 2 以…

AtCoder ABC 108 C - Triangular Relationship (ARC 102 C) (緑色, 300 点)

editorial に載っている解法は整数論で でやっているし、僕も本番それでやったけど、この制約なら全探索でパッと書けるべきですね... 参考: ABC108/ARC102 C: 解説に書かれていませんが、制約が手加減されているので a か a % K の値を全探索できます、この…

AtCoder ABC 105 C - Base -2 Number (水色, 300 点)

なるほど... 問題へのリンク 問題概要 整数 が与えられる。 を "-2 進法" 展開せよ。すなわち が成り立つような整数 と 0-1 整数 を求めよ。 制約 考えたこと 2 進法展開や 10 進法展開なら ここ に書いた通りなん。-2 進法になってもそう大差ないん。 基本…

もこもこさんの整数方程式 x^2 + 3x = y^2

もこもこさんが Twitter で挙げてた問題に色んな解法を寄せられていて面白かったのでメモします。 問題 を満たす整数 をすべて求めよ 解法 1: 判別式が平方数 (Pulmn さんの解法) 恐らく受験数学的には最もメジャーな解法です。 を二次方程式として見たとき…

AOJ 2610 Fast Division (JAG 夏合宿 2013 day3-D) (250 点)

人工的過ぎる設定であまり自然じゃない問題だけど、整数の整除についての注意点を学べる教育的良問なんな。 問題へのリンク 問題概要 整数 が与えられる。 を 回二乗した数より大きい最小の素数を とする。 を で割ったあまりを求めよ。 制約 < 1000 考えた…

AtCoder ABC 103 C - Modulo Summation (茶色, 300 点)

が互いに素でない場合とか一瞬だけ怖くなるけど、信じて提出する!!!!!!! 問題へのリンク 問題概要 個の整数 が与えられる。 様々な非負整数 に対して を で割ったあまり を で割ったあまり を で割ったあまり の総和を考えたとき、その最大値を求めよ…

AtCoder AGC 026 B - rng_10s (青色, 600 点)

あーーーーーー、これは大好物系なん!!!!! 本番でやってみたかったん!!!!! 問題へのリンク 問題概要 (AGC 026 B) 整数 があたえられる。 最初は在庫に 個あって、 毎日 個ずつ消費される その日の最後に 個以下しか残っていなかったら 個補充され…

みんなのプロコン 2018 決勝 A - Uncommon (包除原理)(600 点)

包除原理練習第二弾なん! という制約の意味に気がつくのにかなり時間がかかったん。これのおかげで「 の中に の倍数が何個あるか」というのが、 ではなく でできるのんな。 Uncommon へのリンク 問題概要 個の相異なる整数 と、整数 が与えられる。各 に対…

AOJ 2706 幾何問題を解こう (JAG 夏合宿 2015 day2-A) (200 点)

問題へのリンク 問題概要 整数 があたえられる。 進法で有理数 p/q を小数で表したときに有限小数となるような最小の 2 以上の整数 を求めよ。 制約 < < 考えたこと とりあえず p/q を約分しておく。 そして、q を素因数分解したときの、指数部を全部 1 にし…

AOJ 1276 Prime Gap (ICPC アジア 2007 B) (150 点)

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

AOJ 2353 Four Arithmetic Operations

この問題の既存の解説記事は中国剰余定理によるものが多かったので、それ以外の方法を示すのはいいかもなん。 AOJ 2353 Four Arithmetic Operations 問題概要 有理数列 がある。各項は以下のように定義される: ただし は +、-、×、÷ のいずれかである。 を…