　$S = \lbrace 3, 29, 61, 73 \rbrace$ とする．$S$ に含まれる素数のうち $m$ を割り切るものの集合を $S_{1}$，$m$ を割り切らないものの集合を $S_{2}$ とする．\
　このとき，$p \in S_{1}$ について，$m$ が $p^2$ で割り切れないならば，$m^{k}$ を $p^{2}$ で割った余りは，$k = 1$ のときは $0$ ではない $p$ の倍数となり，$k \geq 2$ のときは $0$ となる．また，$m$ が $p^2$ で割り切れるならば，$m^{k}$ を $p^{2}$ で割った余りは常に $0$ となる．\
　また，$q \in S_{2}$ について，$m$ は $q$ と互いに素であるため，$\textrm{mod} \ q^{2}$ における原始根を $r_{q}$ とすると，
$$m \equiv r_{q}^{t} \ (\textrm{mod} \ q^2)$$

となる整数 $1 \leq t \leq q(q-1)$  が存在することが分かる．このとき，$m^{k}$ を $q^{2}$ で割った余りとしてあり得る整数は全部で 
$$\dfrac{\operatorname{lcm} (t, q(q-1))}{t} = \dfrac{q(q-1)}{\gcd(t, q(q-1))}$$
種類あると分かり，$m^{k}$ を $q^{2}$ で割った余りの周期もこれに一致すると分かる．\
　中国式剰余定理より，$m^{k}$ を $M$ で割った余りは $3^{2}, 29^{2}, 61^{2}, 73^{2}$ それぞれで割った余りの組み合わせに $1$ 対 $1$ 対応する．したがって，$a = |S_{2}|, S_{2} = \lbrace q_{1}, q_{2}, \dots , q_{a} \rbrace$ とし，$h(m)$ を $S_1$ の元 $p$ が存在して $m$ が $p^2$ で割り切れないとき $1$，そうでないとき $0$ を取る値を定めると，$m^{k}$ を $M$ で割った余りとしてあり得る整数の種類数は 
$$
\operatorname{lcm} \left (
\frac{q_1(q_1-1)}{\gcd(t_1, q_1(q_1-1))}, 
\frac{q_2(q_2-1)}{\gcd(t_2, q_2(q_2-1))}, 
\dots , 
\frac{q_a(q_a-1)}{\gcd(t_a, q_a(q_a-1))}
\right) + h(m)$$ 
で表されることが分かる (以下，この式を $(1)$ とする)．いま，$q_{i}(q_{i} - 1)$ は $\dfrac{q_i(q_i-1)}{\gcd(t_i, q_i(q_i-1))}$ の倍数であるから，$ (1)$ は
$$\operatorname{lcm} (3 \times 2, 29 \times 28, 61 \times 60, 73 \times 72) + 1 = 325425241$$
以下である．この値は $\operatorname{lcm} (29 \times 28, 61 \times 60, 73 \times 72)+1$ にも等しいことに注意すると，$m$ がこれを実現するための条件は，
- $S_{1} = \lbrace 3 \rbrace , S_{2} = \lbrace 29, 61, 73 \rbrace$ である．
- $m$ は $9$ の倍数でない．
- $\dfrac{29 \times 28}{\operatorname{gcd}(t_1, 29 \times 28)}, \dfrac{61 \times 60}{\operatorname{gcd}(t_2, 61 \times 60)}, \dfrac{73 \times 72}{\operatorname{gcd}(t_3, 73 \times 72)}$ がぞれぞれ $29 \times 7, 61 \times 5, 73 \times 2^{3} \times 3^{2}$ を約数に持つ

である (最後の条件は素因数ごとにみれば得られる)．これは実現可能なので，$X$ は上の値である．また，$m$ が上の条件を満たすとき $m$ を $3^{2}, 29^{2}, 61^{2}, 73^{2}$ で割った余りとしてあり得る値の種類数をそれぞれ $Y_3, Y_{29}, Y_{61}, Y_{73}$ とすると，
$$\begin{aligned}
Y_3 &= 2\\\\
Y_{29} &= \sum_{29\times 7\mid d\mid 29\times 28}\varphi(d)
= \varphi(29)\varphi(7)\sum_{d\mid 4}\varphi(d)
= 4\varphi(29)\varphi(7) = 672\\\\
Y_{61} &= \sum_{61\times5\mid d\mid 61\times 60}\varphi(d)
= \varphi(61)\varphi(5)\sum_{d\mid 12}\varphi(d)
= 12\varphi(61)\varphi(5) = 2880\\\\
Y_{73} &= \varphi(73\times72) = 1728
\end{aligned}$$
である．ただし，上の計算では $\varphi$ が乗法的であることや $\displaystyle\sum_{d\mid n}\varphi(d) = n$ が任意の正整数 $n$ について成り立つことを用いた．よって，中国式剰余定理より $Y = Y_3Y_{29}Y_{61}Y_{73} = 6688604160$ と分かる．\
　以上より，解答すべき値は $X + Y = \mathbf{7014029401}$ である．
公式解説
https://onlinemathcontest.com/contests/omc236/editorial/10480
　正整数 $n, N$ に対して，$n, n^2, n^3, n^4, \ldots$ を $N$ で割った余りとして現れる値の種類数を $f(n, N)$ とします．また $M = 3^2 \cdot 29^2 \cdot 61^2 \cdot 73^2$ とします．\
　正整数 $m$ に対して $f(m, M)$ の取り得る最大値を $X$ とし，$1 \leq m \leq M-1$ を満たす $m$ のうち $f(m, M) = X$ を満たすものの個数を $Y$ とするとき，$X+Y$ の値を解答してください．