简要题意
\(T\) 组数据，每组数据给出两个整数 \(N,M\)，求：
\[\sum_{i=1}^{N}\sum_{j=1}^{M}{[\gcd(i,j)\in\mathbb{P}]} \]\(1\leq N,M\leq10^7,T\leq10\)
思路
将原式改为改为枚举 \(\gcd(i,j)\)，将原式改为：
\[\sum_{p\in\mathbb{P}}\sum_{i=1}^{N}\sum_{j=1}^{M}[\gcd(i,j)=p] \]将 \(i,j\) 中的 \(p\) 约去，得：
\[\sum_{p\in\mathbb{P}}\sum_{i=1}^{\lfloor\frac{N}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{p}\rfloor}[\gcd(i,j)=1] \]把右边的 \(\gcd\) 判定改为莫比乌斯函数求和形式，得：
\[\sum_{p\in\mathbb{P}}\sum_{i=1}^{\lfloor\frac{N}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{p}\rfloor}\sum_{q\mid \operatorname{lcm}(i,j)}\mu(q) \]\(q\) 在后面不好变形，我们将其提到前面来，容易看出 \(q\) 的上界为 \(\min\{\lfloor\frac{N}{p}\rfloor,\lfloor\frac{M}{p}\rfloor\}\)，提到前面后还要注意只有 \(q\mid i\) 且 \(q\mid j\) 才需要累加。得：
\[\sum_{p\in\mathbb{P}}\sum_{q=1}^{\min\{\lfloor\frac{N}{p}\rfloor,\lfloor\frac{M}{p}\rfloor\}}\sum_{i=1}^{\lfloor\frac{N}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{p}\rfloor}(\mu(q)\cdot[q\mid i][q\mid j]) \] 标签：lfloor,mathbb,frac,gcd,sum,rfloor,SPOJ,Table,Primes From： https://www.cnblogs.com/zheyuanxie/p/spoj-pgcd.html