答えは 1+∑i=1Ngcd(i,M)\displaystyle 1 + \sum_{i = 1}^{N} \mathrm{gcd}(i, M)1+i=1∑Ngcd(i,M) です。
gcd(i,M)=d\mathrm{gcd}(i, M) = dgcd(i,M)=d となる i (1≤i≤N)i \ (1\leq i\leq N)i (1≤i≤N) の数を dp[d]dp[d]dp[d] とします。
すると、∑i=1Ngcd(i,M)=∑d∣Md×dp[d]\displaystyle \sum_{i = 1}^{N} \mathrm{gcd}(i, M) = \sum_{d | M} d\times dp[d]i=1∑Ngcd(i,M)=d∣M∑d×dp[d] です。
D′D'D′ を d∣d′d|d'd∣d′ かつ d′∣Md'|Md′∣M である d′d'd′ の集合として、dp[d]=Nd−∑d′∈D′dp[d′]\displaystyle dp[d] = \frac{N}{d} - \sum_{d'\in D'}dp[d']dp[d]=dN−d′∈D′∑dp[d′] と計算することができるので、ddd が大きい順に埋めていくことができます。
時間計算量は O(M+{d(M)}2)O(\sqrt{M} + \{d(M)\}^2)O(M+{d(M)}2) です。