"142857" はエニアグラムやっていたら毎日目にする。エニアグラムは競プロの役に立つ！ 問題へのリンク 問題概要（output only） 正整数 と文字列 の組であって以下の条件を全て満たすものを 1 つ挙げよ。 は 0 から 9 までの数字からなる長さ 5000 以下の文…

この問題を思い出した！ 問題へのリンク 問題概要 素数 と、 個の 1 以上 以下の整数 が与えられる。 を満たす整数 が存在するような の組の個数を数え上げよ。 制約 考えたこと 一瞬、原始根を考えたくなったが、原始根ではなく「位数」を考えた方が計算量…

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

原始根 + NTT 問題へのリンク 問題概要 素数 と、数列 、 が与えられる。 各整数 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 添字積 convolution はできるのかと一瞬戸惑う。しかし が素数であることに着目すると、原始根 を介…

AGC っぽくない気がするけど、好き 問題へのリンク 問題概要 とする (素数である)。 個の非負整数 が与えられる。 の値を求めよ。 制約 考えたこと 「和を で割ったあまり」ではなく、「 で割ったあまりの和」であることに注意。それでも、とりあえず以下の…

最初誤読して、「何度でもスタート地点にワープして戻っても良い」というバージョンの問題を解いていた。 問題へのリンク editorial 問題概要 個の整数 と 2 以上の整数 が与えられる。 頂点からなる以下のような有向グラフであって、頂点 1 を始点として、…

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

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

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