原式可以化为

$\displaystyle{\sum_{p \in primes}\sum_{i = 1}^n\sum_{j = 1}^m[(i, j) = p]}$

注意到，$[(i, j) = p] = [\frac{(i, j)}{p} = 1] = [(\frac{i}{p}, \frac{j}{p}) = 1]$，因此原式进一步化为

$\displaystyle{\sum_{p \in primes}\sum_{i = 1}^n\sum_{j = 1}^m\sum_{d \mid (\frac{i}{p}, \frac{j}{p})}\mu(d)}$

我们交换求和顺序，有

$\displaystyle{\sum_{p \in primes}\sum_{d = 1}\mu(d)\sum_{i = 1}^n[d \mid \frac{i}{p}]\sum_{j = 1}^m[d \mid \frac{j}{p}]}$

注意到，$1 \sim \frac{n}{p}$ 中 $d$ 的倍数有  $\left \lfloor \frac{\frac{n}{p}}{d} \right \rfloor = \left \lfloor \frac{n}{dp} \right \rfloor$ 个，因此有

$\displaystyle{\sum_{p \in primes}\sum_{d = 1}^{\min(\frac{n}{p}, \frac{m}{p})}\mu(d) \left \lfloor \frac{n}{dp} \right \rfloor\left \lfloor \frac{m}{dp} \right \rfloor}$

令 $t = dp$，我们在外层枚举 $t$

$\displaystyle{\sum_{t = 1}^{\min(n, m)} \left \lfloor \frac{n}{t} \right \rfloor\left \lfloor \frac{m}{t} \right \rfloor \sum_{p \in primes, p \mid t} \mu(\frac{t}{p})}$

我们维护一个 $\mu$ 的前缀和就可以了，具体来说，我们维护一个数组 $S$ ，枚举 $p, t$ ，如果  $p \mid t$ 就令 $S_k \gets S_k + \mu(\frac{t}{p})$，然后接下来就正常的维护前缀和就行了。

注意该题数据规模很大，需要进行一些优化(比如不该开 long long 的地方用 int)。