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

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

素因数分解

AtCoder ABC 114 D - 756 (400 点)

editorial は「75」という整数の特徴をフル活用している。 そして 75 という整数の特徴を活用しない DP による方法もあると説いている。 ここでは 75 という整数の特徴も活用せず、DP もしない (といっても DP への改良は容易) 愚直な全探索でも通った。 問…

Tenka1 2019 E - Polynomial Divisors (800 点)

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

AOJ 2720 Identity Function (AOJ-ICPC 450 点)

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

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

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

AOJ 3062 Product (RUPC 2019 day2-L)

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

QUPC 2018 I - Buffalo

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

Codeforces AIM Tech Round 5 F - Make Symmetrical

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

CADDi 2018 C - Product and GCD (300 点)

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

AtCoder ARC 004 D - 表現の自由

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

AtCoder AGC 003 D - Anticube (1100 点)

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

Codeforces 511 DIV1 A - Enlarge GCD

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

AtCoder ABC 110 D - Factorization (400 点)

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

AtCoder ARC 034 C - 約数かつ倍数

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

AOJ 2706 幾何問題を解こう

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