**補題1.**　$S(1,n)$ が平方数であることは, $n$ が $2$ べきであることと同値である.

**証明.**　$\varphi$ をEulerのトーシェントとし, $n$ のもつ素因数 $p_1\lt p_2\lt\cdots\lt p_k$ について $p_k\gt 2$ と仮定する. このとき, $r$ が $n$ と互いに素ならば $n-r$ も互いに素であることから,
$$S(1,n)=n\times\dfrac{\varphi(n)}{2}=\dfrac{n^2}{2}\prod_{i=1}^{k}\dfrac{p_i-1}{p_i}$$
これより $S(1,n)$ が $p_k$ で割り切れる回数は奇数であることがわかるから, 特に $S(1,n)$ は平方数となり得ない.\
　逆に, $n$ が $2$ べきならば $S(1,n)=(n\/2)^2$ であるから, 特にこれは平方数である.

**補題2.**　$S(m,n)=m^2S(1,n)$

**証明.**　$(a-1)n$ より大きく $an$ 以下の整数であって, $n$ と互いに素なものの総和は, 補題1の証明と同様の要領で
$$ (a-1)n\times\varphi(n)+S(1,n)=\left(a-\dfrac{1}{2}\right)n\varphi(n)=(2a-1)S(1,n) $$
と計算できる (これは $n=2$ でも正しい). 上式を $a=1,\cdots,m$ について足し合わせることで, 所望の結論を得る.

　以上より, 解答すべき値は $\displaystyle\frac{1}{10^6}\sum_{m=1}^{10^6}\sum_{N=1}^{19} m2^N=\textbf{524287524287}$ である.
公式解説
https://onlinemathcontest.com/contests/omc030/editorial/236
　$m,n$ を $10^6$ 以下の正整数とします. ただし $n$ は $1$ ではないとします.\
　$n$ と互いに素な $mn$ 以下の正整数の総和を $S(m,n)$ とおいたとき, $S(m,n)$ が平方数となるような組 $(m,n)$ すべてについて $mn$ の総和を $T$ とします. $\dfrac{T}{10^6}$ を解答してください.