Euler関数
AtCoder
AtCoder600点
ABC-G
黄色diff
数学(整数問題)
原始根
Fermatの小定理
Euler関数
最大公約数
互いに素
約数
入力が定数個
素数
位数の法則
解空間:O(N^2)通りの選択肢
テク:約数の個数は少ない
ある量を固定して考える
条件の言い換え
変数変換して扱いやすい同型な問題を見出す
原始根が絡む問題は時々出るイメージですね。 問題へのリンク 問題概要 素数 が与えられます。 次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。 ある正の整数 が存在して、 が成立する 制約 は素数 考えたこと 整数問題とい…
AtCoder
AtCoder500点
ABC-E
数学(整数問題)
拡張Euclidの互除法
最大公約数
数珠
水色diff
Euler関数
Giant-Step Baby-Step法
中国剰余定理
マルチテストケース問題
一次合同方程式を解く問題です! 問題へのリンク 問題概要 円周上に 個の椅子が並べられています。そのうち 1 つは玉座です。 高橋君は最初、玉座から時計回りに数えて 個隣の椅子に座っており、次の行動を繰り返します。 行動:いま座っている椅子から時計…
教育的だと思ったのでメモだけ。 問題へのリンク 問題概要 整数 が与えられる。 以上 未満の整数 であって を満たすものの個数を求めよ。 解法 の最大公約数を として のオイラー関数値が答え。 #include <iostream> #include <sstream> #include <cstdio> #include <cstdlib> #include <cmath> #include <ctime></ctime></cmath></cstdlib></cstdio></sstream></iostream>…