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

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

Fermatの小定理

AtCoder ABC 212 G - Power Pair (黄色, 600 点)

原始根が絡む問題は時々出るイメージですね。 問題へのリンク 問題概要 素数 が与えられます。 次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。 ある正の整数 が存在して、 が成立する 制約 は素数 考えたこと 整数問題とい…

AOJ 2213 多項式の解の個数 (UTPC 2010 J)

今日の以下の類題 drken1215.hatenablog.com 解説はここに書いた。 qiita.com コード 形式的冪級数を用いてみた。 // // Formal Power Series (on runtime mod) // // verified: // Yosupo Judge // https://judge.yosupo.jp/problem/inv_of_formal_power_se…

Tenka1 2019 E - Polynomial Divisors (橙色, 800 点)

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

てんぷらたんの双子素数問題

TL で見たので 問題へのリンク 問題概要 双子素数 が与えられる。 を で割ったあまりと、 を で割ったあまりをそれぞれ出力せよ。 制約 解法 1: Wilson の定理 簡単のため、適切に swap して とする。 Wilson の定理というのがあり、 を素数として が成立す…

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

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

AOJ 3062 Product (RUPC 2019 day2-L)

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

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

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

Codeforces #460 (Div. 2) E. Congruence Equation (R2100)

中国剰余定理のことをあれこれ調べていたら勢いで解いたん 問題へのリンク 問題概要 整数 が与えられる。 mod. ) が成立するような 以上 以下の整数 を数え上げよ。 制約 は素数 < 解法 Fermat の小定理から以下のことが言える: は mod. において周期 である…