元の問題文

正整数 $N$ が与えられます。
1以上 $N$ 未満の整数で $N$ と互いに素な整数の総和を出力してください。
$A$ と $B$ が互いに素とは $A$ と $B$ の最大公約数が1であることです。

$T$ 個のテストケースが与えられるので、それぞれについて答えを出力してください。

想定エスパー法

入力の $N$ が素数である場合、答えが $\displaystyle \frac{1}{2}N(N-1)$ であることに注目します。
ここで答えは1以上 $N$ 未満の何かしらの条件を満たす整数の総和であるとエスパーします。
また $N$ が素数であるときは $N$ 未満の整数すべてが条件を満たすことをエスパーします。

次にすべての入力について、答えが $N$ の倍数になっていることに注目します。
ここから条件を満たす1以上 $N$ 未満の整数 $k$ と $N-k$ の総和であるとエスパーします。

さらに $N$ が素数 $p$ と整数 $m$ を用いて $p^m$ と表せるとき、答えが $\displaystyle \frac{1}{2}N(N-p^{m-1})$ となっていることに注目します。
またサンプルに高度合成数である 720720 が存在します。
ここから答えは $N$ の素因数が関わっていることをエスパーします。

$N$ が2つ以上の素因数をもつ合成数であるとき、包除原理を用いるとうまくいくことがわかります。

これらから答えが $N$ と互いに素である整数の総和であることをエスパーします。

解法

ひとつの入力における $N$ の総和は $10^6$ 以下なので愚直に $N$ と互いに素なものを求めることができます。