解説

答えは $\displaystyle 1 + \sum_{i = 1}^{N} \mathrm{gcd}(i, M)$ です。

$\mathrm{gcd}(i, M) = d$ となる $i \ (1\leq i\leq N)$ の数を $dp[d]$ とします。

すると、$\displaystyle \sum_{i = 1}^{N} \mathrm{gcd}(i, M) = \sum_{d | M} d\times dp[d]$ です。

$D'$ を $d|d'$ かつ $d'|M$ である $d'$ の集合として、$\displaystyle dp[d] = \frac{N}{d} - \sum_{d'\in D'}dp[d']$ と計算することができるので、$d$ が大きい順に埋めていくことができます。

時間計算量は $O(\sqrt{M} + \{d(M)\}^2)$ です。