　$1$ から $100$ の番号が付いた $100$ 個の頂点について, $pe\overbrace{p...p}^{n}er$ さんが素直ならば頂点 $n$ を白で塗り, $pe\overbrace{p...p}^{n}er$ さんが照れ屋さんならば頂点 $n$ を黒で塗る. さらに, 頂点 $n$ から頂点 $a_n$ へ有向辺を張ったグラフを考える. このグラフにおいて, どの辺も両端の頂点の色は異なり, どの頂点もただ一つの $2$ より大きな偶数個の頂点からなる閉路に含まれている. したがって, 特に白い頂点の数と黒い頂点の数は等しいことに注意する. 

----
**補題.**　白い頂点 $W_1,W_2,\dots,W_n$ と黒い頂点 $B_1,B_2,\dots,B_n$ がある. このとき, これらの頂点の間に $2n$ 本の有向辺を張る方法であって, どの辺も両端の頂点の色は異なり, どの頂点もただ一つの偶数個の頂点からなる閉路に含まれているものは, $(n!)^2$ 通りある.\
**証明.**　$W_i$ から出る辺の行き先を $B_{p_i}$, $B_i$ から出る辺の行き先を $W_{q_i}$ とすると, 
$p_1,p_2,\dots,p_n$ と $q_1,q_2,\dots,q_n$ はそれぞれ $1,2,\dots,n$ の置換である. 
また, 異なるグラフについて異なる置換が得られる. \
　逆に, $p_1,p_2,\dots,p_n$ と $q_1,q_2,\dots,q_n$ をそれぞれ $1,2,\dots,n$ の置換とすると, 
$W_i\to B_{p_i}$, $B_i\to W_{q_i}$ と辺を張ることで, 条件をみたすグラフとなる. \
　したがって, 条件をみたすグラフと置換 $\\{p_i\\},\\{q_i\\}$ の組は一対一対応するから, 示された. 

---

　以下, $m$ を求めるため, 頂点の色を固定し, 包除原理を用いる. 
黒と白の頂点 $1$ つずつからなる閉路 $k$ 個の選び方は $\left({}\_{50}\mathrm{C}\_k\right)^2k!$ 通りであるから
$$
m = {}\_{100}\mathrm{C}\_{50}\times \sum\_{k = 0}^{50} (-1)^k\left({}\_{50}\mathrm{C}\_k\right)^2k!\bigl((50 - k)!\bigr)^2 = 100!\times \sum_{k = 0}^{50}\frac{(-1)^k}{k!}
$$
を得る. 従って, それぞれの素数について計算することで求める答えは $50+26+12+10=\bf{98}$ である.
公式解説
https://onlinemathcontest.com/contests/omc074/editorial/1698
　最後に運営さんから補足があるので是非そちらを併せて読んでください．

----

　$1,2,\cdots, 100$ を頂点とし $n$ から $a_n$ に辺を張った有向グラフを考える．このとき条件より各連結成分は周期が $4$ 以上の偶数のサイクルであり，サイクルが $k$ 個のとき村人の性格は $2^k$ 通りある．\
　例として周期 $4$ のサイクルが $22$ 個，$6$ のサイクルが $2$ 個の場合を考えよう．このとき問題の組み合わせは
$$\frac{100!}{(4!)^{22}\times (6!)^2}\times \frac{1}{22!\cdot 2!} \times (3!)^{22}\times (5!)^2\times 2^{22+2}=\frac{100!}{2^{22}\times 3^2}\times \frac{1}{22!\cdot 2!}$$
通りである．ここで，右辺をさらに以下のように変形する：
$$\frac{100!}{24!}\times \frac{1}{2^{22}\times 3^2}\times \frac{24!}{22!\cdot 2!}$$
このとき以下に留意する：
- $2\times 22+3\times 2=50$
- 第3項は $22$ 個の $2$ と $2$ 個の $3$ を並べ替える方法の総数になっている．

　この要領で，連結成分の個数が $k$ 個である場合，問題の組み合わせの総数は以下の形式的冪級数の $x^{50}$ の係数で与えられることが分かる．
$$\frac{100!}{k!}\left(\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\cdots\right)^k$$
これを $k=1,2,\cdots$ について足し合わせることで，結局求めるべき $m$ は以下で表される $Q(x)$ の $x^{50}$ の係数で与えられる．
$$P(x)=\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\cdots,　Q(x)=\frac{100!}{1!}P(x)+\frac{100!}{2!}P(x)^2+\frac{100!}{3!}P(x)^3\cdots$$
ここで $P^\prime (x) = x+x^2+x^3+\cdots$ だから
$$\begin{aligned}
Q^\prime(x)&=P^\prime (x) \left(\frac{100!}{0!}+\frac{100!}{1!}P(x)+\frac{100!}{2!}P(x)^2+\cdots\right) \\\\
&= (x+x^2+x^3+\cdots)(100!+Q(x))
\end{aligned}$$
$Q(x)=a_0+a_1 x+ a_2 x^2+\cdots$ とおけば $m=a_{50}$ であり，
$$\begin{aligned}
Q^\prime(x) &= a_1+2a_2x+3a_3x^2+\cdots \\\\
&= (a_0+100!)x+(a_0+a_1+100!)x^2+(a_0+a_1+a_2+100!)x^3+\cdots
\end{aligned}$$
係数比較と $a_0=a_1=0$ より以下が得られる：
$$a_2=\frac{100!}{2},　a_3=\frac{100!}{3},　a_{k+2}=\frac{100!+\sum_{i=2}^{k} a_i}{k+2}　(k=2,3,\cdots)$$
あとは $a_{50}$ が $2,3,5,7$ でそれぞれ割り切れる回数を求めればよい．$b_n=\dfrac{a_n}{100!}$ とおけば，帰納的に $b_n$ は以下に等しいことが分かる：
- 正整数からなる狭義単調減少な有限数列であって，初項が $n$ であり，連続する $2$ 項の差が常に $2$ 以上であるようなものすべてについて，項の総積の逆数を足し合わせた値．

例えば $n=6$ のときは
$$b_6=\frac{1}{6\times 4\times 2}+\frac{1}{6\times4}+\frac{1}{6\times 3}+\frac{1}{6\times 2}+\frac{1}{6}$$
である．以下 $2,3,5,7$ それぞれについて $b_{50}$ のオーダーを考える（便宜上負の値も考える）．
- $2$ のとき $\\{50,48,46,\cdots,2\\}$ のときのみオーダーが最小値 $-47$ を取り，$b_{50}$ のオーダーは $-47$ である．
- $3$ のとき $\\{50,48,45,\cdots,3\\}$ のときのみオーダーが最小値 $-22$ を取り，$b_{50}$ のオーダーは $-22$ である．
- $5$ のとき
$$\\{50,※,45,※,40,\cdots,10,※,5,※\\}$$
の形式で表される数列のときにオーダーが最小値 $-12$ を取り，$b_{50}$ のオーダーも $-12$ であることが計算により確認できる．
- $7$ のとき
$$\\{50,※,42,※,35,\cdots,14,※,7,※\\}$$
の形式で表される数列のときにオーダーが最小値 $-6$ を取り，$b_{50}$ のオーダーも $-6$ であることが計算により確認できる．

以上より，求める値は $(97-47)+(48-22)+(24-12)+(16-6)=\textbf{98}$ である．

----

（運営補足）形式的冪級数として $P,Q$ は次のように計算でき，これより本解説における $m$ の表式を得ることもできます．
$$\begin{aligned}
P(x)&=-\log(1-x)-x,\\\\
Q(x)&=100!(e^{P(x)}-1)\\\\
&=100!\left(\dfrac{e^{-x}}{1-x}-1\right)\\\\
&=100!\left(\sum_{k\geq 0}\dfrac{(-x)^k}{k!}\right)\left(\sum_{k\geq 0}x^k\right)-100!\\\\
&=100!\sum_{n\geq 1}\left(\sum_{0\leq k\leq n}\dfrac{(-1)^k}{k!}\right)x^n
\end{aligned}$$
ユーザー解説
https://onlinemathcontest.com/contests/omc074/editorial/1698/70
　$peer$ 村には, $peper$ さん, $pepper$ さん, ... , $pe\overbrace{p...p}^{100}er$ さんの $100$ 人が住んでいます. $peer$ 村の住人の性格はどれも**素直**か**照れ屋さん**であり, 性格が素直な者は常に素直に本当のことを言い, 照れ屋さんは常に照れて嘘をついてしまいます. また, $peer$ 村の住人はどの二人も互いの性格が素直であるか照れ屋さんであるかを把握しています.\
　ある時, $peer$ 村に旅人がやってきました. 旅人は, まず $1,2,...,100$ を並び替えた順列 $a_1,a_2,...,a_{100}$ であって $a_{a_n}\neq n$ を常にみたすものを適当に定め, そして $100$ 以下の正の整数 $n$ それぞれに対して, $pe\overbrace{p...p}^{n}er$ さんに

- $pe\overbrace{p...p}^{a_n}er$ さんは照れ屋さんですか？

と質問しました. すると, すべての村人が「はい」と回答しました.\
　このとき, 「旅人の定めた $\lbrace a_n\rbrace$ と村人たちの性格」の組み合わせとして考えられるものは $m$ 個あります. $m$ が $10$ 以下の素数で割り切れる回数の総和を求めてください. 例えば, $m = 2^3 \times 3^5 \times7\times11$ であれば $9$ です.