　まず，$f(n,m)$ について考察する．$m^n$ 個の数列のうち，特に各項が $k$ の倍数であるものは $\lfloor m\/k \rfloor ^ n$ 個存在するが，その中には最大公約数が $2k$ や $3k$ などといったものも含まれているため，愚直には足し合わせられない．そこで，整数列 $p=(p_1,p_2,\dots)$ であって，以下の条件をみたすものがあったとしよう：

- 任意の正整数 $n$ に対して，$\displaystyle\sum_{d\mid n}^{} p_d = n$ をみたす．

すると，各項が $k$ の倍数であるような数列を $p_k$ 回重ねて勘定することで，すべての数列に対してちょうど最大公約数分の寄与が与えられる．実際，最大公約数が $k$ である数列に対して，$k$ の約数を $d_1,d_2,\dots,d_t$ とするとそれは $p_{d_1}+\cdots+p_{d_t}$ 回カウントされていて，$p$ の定義よりこれは $k$ に等しい．\
　さて，$p$ について考察する．結論から述べれば，Euler の totient関数 $\varphi$ が $p$ としての条件をみたす．実際，任意の $n$ の約数 $d$ に対して，$1 \le i \le n$ かつ $\gcd(i,n) = d$ をみたす整数 $i$ は $\varphi(n\/d)$ 個存在するので，
$$ \sum_{d\mid n}^{} \varphi(d) = \sum_{d\mid n} \varphi\left(\frac{n}{d}\right) = n $$
が成り立つ．ただし，一つ目の等号では $d$ を $n\/d$ におきかえた．以上より数列 $(a_1,\dots,a_{g(m)})$ には，各 $1 \le i \le m$ に対して $\lfloor m\/i \rfloor$ が $\varphi(i)$ 個ずつ含まれており，$g(m)=\varphi(1)+\cdots+\varphi(m)$ である．特に，
$$g(1001) - g(999) = \varphi(1001) + \varphi(1000) = 720 + 400 = \textbf{1120}.$$
公式解説
https://onlinemathcontest.com/contests/omc198/editorial/8686
　長さ $n$ かつ各項が $1$ 以上 $m$ 以下であるような正整数列 $m^n$ 個すべてに対して，$n$ 数の最大公約数の総和を $f(n,m)$ とおきます．このとき，正整数 $m$ それぞれに対して，以下をみたす正整数 $g(m)$ および広義単調増加な正整数列 $(a_1,a_2,\dots,a_{g(m)})$ が一意に定まります：

- 任意の正整数 $n$ に対して，$a_1^n + a_2^n +\cdots+ a_{g(m)}^n = f(n,m)$ が成り立つ．

　このとき，$g(1001) - g(999)$ の値を求めてください．