| For All Solvers
OMC182

OMC182(F)

ユーザー解説 by Tempurabc

　ord2(f(n))\mathrm{ord}_2(f(n)) の求め方についてです．
　数学的に好ましい方法ではない（厳密性に欠ける）のですが，この手の整数論の問題は公式解説のように乗法的関数が絡む可能性が高いので，nn の素因数が 11 個の場合，素因数が 22 個の場合を考えて，そこから帰納的に推測することも可能です．以下，実際に計算してみます．
　n=pxn=p^x とすると， f(n)=1×n(1−1p)+p×n(1p−1p2)+p2×n(1p2−1p3)+⋯+px−1×n(1px−1−1px)+px=n{(1−1p)x+1}\begin{aligned} f(n) &= 1×n \left( 1-\dfrac{1}{p}\right)+p×n \left( \dfrac{1}{p}-\dfrac{1}{p^2}\right)+p^2×n \left( \dfrac{1}{p^2}-\dfrac{1}{p^3}\right)+ \cdots +p^{x-1}×n\left( \dfrac{1}{p^{x-1}}-\dfrac{1}{p^x}\right)+p^x \\ & = n \left\lbrace \left( 1-\dfrac{1}{p}\right)x+1 \right\rbrace \end{aligned} 　n=pxqyn=p^x q^y とすると（ここがやや難しいです），

f(n)=∑i≦x−1,j≦y−1piqj×n(1pi−1pi+1)(1qj−1qj+1)+∑i=x,j≦y−1pxqj×n⋅1px(1qj−1qj+1)+∑i≦x−1,j=ypiqy×n⋅1qy(1pi−1pi+1)+pxqy=xyn(1−1p)(1−1q)+yn(1−1q)+xn(1−1p)+n=n{(1−1p)x+1}{(1−1q)y+1}\begin{aligned} f(n) & = \sum_{i≦x-1,j≦y-1} p^i q^j×n \left( \dfrac{1}{p^i}-\dfrac{1}{p^{i+1}}\right)\left( \dfrac{1}{q^j}-\dfrac{1}{q^{j+1}}\right) \\ & + \sum_{i=x,j≦y-1} p^x q^j×n \cdot \dfrac{1}{p^x}\left( \dfrac{1}{q^j}-\dfrac{1}{q^{j+1}}\right) +\sum_{i≦x-1,j=y} p^i q^y×n \cdot \dfrac{1}{q^y}\left( \dfrac{1}{p^i}-\dfrac{1}{p^{i+1}}\right) +p^xq^y\\ & = xyn\left( 1-\dfrac{1}{p}\right)\left( 1-\dfrac{1}{q}\right)+yn\left( 1-\dfrac{1}{q}\right)+xn\left( 1-\dfrac{1}{p}\right)+n\\ & = n\left\lbrace \left( 1-\dfrac{1}{p}\right)x+1 \right\rbrace\left\lbrace \left( 1-\dfrac{1}{q}\right)y+1 \right\rbrace \end{aligned} 　以上の結果より，n=p1x1p2x2⋯n=p_1^{x_1} p_2^{x_2} \cdots であれば，f(n)=n{(1−1p1)x1+1}{(1−1p2)x2+1}⋯f(n)=n\left\lbrace \left( 1-\dfrac{1}{p_1}\right)x_1+1 \right\rbrace\left\lbrace \left( 1-\dfrac{1}{p_2}\right)x_2+1 \right\rbrace \cdots であると推測できます．
　公式解説とは見た目が全く違いますが，上式が ∏p∣npordp(n)−1((p−1)ordp(n)+p)\prod\limits_{p|n}p^{\mathrm{ord}_p(n)-1}((p-1)\mathrm{ord}_p(n)+p) と一致しています．