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

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

互いに素

AtCoder ABC 161 F - Division or Substraction (600 点)

めちゃくちゃ面白かった!!! 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす 以上 以下の整数 の個数を求めよ。 整数 を用いて、 に対して操作を行っていく が で割り切れるならば を で置き換えて、そうでない場合には を に置き換える…

AtCoder ABC 158 E - Divisible Substring (500 点)

こういう問題を求めてた!! 問題へのリンク 類題として、こんなのがある。 drken1215.hatenablog.com 問題概要 長さ の、各文字が '0'〜'9' のいずれかとなっている文字列 と、素数 が与えられる。 の空でない連続する区間であって、その整数が で割り切れ…

Educational Codeforces Round 81 D. Same GCDs (R1800)

教育的だと思ったのでメモだけ。 問題へのリンク 問題概要 整数 が与えられる。 以上 未満の整数 であって を満たすものの個数を求めよ。 解法 の最大公約数を として のオイラー関数値が答え。 #include <iostream> #include <sstream> #include <cstdio> #include <cstdlib> #include <cmath> #include <ctime></ctime></cmath></cstdlib></cstdio></sstream></iostream>…

Codeforces #613 (Div. 2) F. Classical? (R2800)

勉強になった...けど、これ知らずにできるもんなの!? 問題へのリンク あと、LCM の最小値バージョンもある! drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …

AtCoder ABC 142 D - Disjoint Set of Common Divisors (400 点)

すごく楽しくて教育的な整数問題 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 の公約数から何個か整数を選ぶことを考える。 選んだ整数からどの 2 つをとっても、それらが互いに素になるようにしたい。 選べる個数の最大値を求めよ。 制約 考え…

AtCoder AGC 001 B - Mysterious Light (500 点)

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

AOJ 2720 Identity Function (AOJ-ICPC 450 点)

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

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

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

AtCoder ARC 102 C - Triangular Relationship (300 点)

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

AOJ 2610 Fast Division

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

AtCoder ABC 100 C - *3 or /2 (300 点)

今週のお題「2018年上半期」 好きなのん ABC 100 C - *3 or /2 問題概要 N 個の整数 a1, a2, ..., aN があって 1 回の操作で以下が行える 各整数について「3 倍」「2 で割るなら 2 で割る」のいずれかを行う どれかの整数については「2 で割る」の方をしなけ…