DarkBZOJ传送门

洛谷传送门

解析：

应教练要求开始准备数论讲义，如今把开通博客以前的写一些数论题目给弄上来。html

显然题目要求的是这个东西： $\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)\mathrm{is\text{ }a\text{ }prime}]$c++

接下来以 $\mathbb{P}$表示素数集合，下面是化简过程。
$Ans=\sum_{p\in \mathbb{P}}\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p]$git

定义函数 $f$和 $F$以下： $f(p)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p]$ $F(p)=\sum_{i=1}^n\sum_{j=1}^m[p\mid gcd(i,j)]$web

很显然咱们有 $F(p)=\sum_{p\mid d}f(d)$ $F(p)=\lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{p}\rfloor$app

接下来考虑莫比乌斯反演
$f(p)=\sum_{p\mid d}\mu(\frac{d}p)F(d)$svg

$\begin{aligned} Ans=&\sum_{p\in \mathbb{P}}f(p)\\ =&\sum_{p\in \mathbb P}\sum_{p\mid d}\mu(\frac{d}{p})F(d)\\ =&\sum_{p\in \mathbb P}\sum_{d=1}^{\lfloor\frac{ \min(n,m) }p\rfloor}\mu(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor \end{aligned}$函数

反演后看着这个神仙式子不少人就想放弃了。spa

不虚啊，虚什么。
这个 $dp$很烦是吧，那就交换枚举顺序啊code

$\begin{aligned} Ans=&\sum_{D=1}^{\min(n,m)}\sum_{p\mid D,p\in \mathbb P}\mu(\frac{D}{p})\lfloor\frac{n}D\rfloor\lfloor\frac{m}D\rfloor\\ =&\sum_{D=1}^{\min(n,m)}\lfloor\frac{n}D\rfloor\lfloor\frac{m}D\rfloor(\sum_{p\mid D,p\in\mathbb P}\mu(\frac{D}p)) \end{aligned}$orm

设： $g(D)=\sum_{p\mid D,p\in \mathbb P}\mu(\frac{D}p)$

显然咱们只须要筛出全部的 $\mu$函数就能够枚举每一个质数，在 $O(n\log\log n)$时间内处理出全部 $g$函数的值，以后维护一下 $g$的前缀和，而后整除分块就好了。

可是实际上， $g$也能够在线性筛的时候一块儿处理出来（虽然它并非积性函数）

首先 $g(1)=0$

对于一个质数 $p$， $g(p)=\mu(1)=1$

剩下的分状况考虑，若是 $p\nmid n$，那么 $p$就是增长的一个质因子，那么原来全部有贡献的 $\mu$都要 $\times -1$，并且会带入一个新的贡献 $\mu(n)$，因此有 $g(np)=\mu(n)-g(n)$

若是已经有了 $p\mid n$，那么除了 $\mu(n)$其余全部变量中都有 $p^2$因此剩余的只有 $\mu(n)$了。

具体实现就请自行参考代码里面的了吧。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define gc get_char
#define pc putchar
#define cs const

namespace IO{
	namespace IOONLY{
		cs int Rlen=1<<18|1;
		char buf[Rlen],*p1,*p2;
	}
	inline char get_char(){
		using namespace IOONLY;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	
	inline int getint(){
		re int num;
		re char c;
		while(!isdigit(c=gc()));num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return num;
	}
	inline void outint(ll a){
		static char ch[23];
		if(a==0)pc('0');
		while(a)ch[++ch[0]]=a-a/10*10,a/=10;
		while(ch[0])pc(ch[ch[0]--]^48);
	}
}
using namespace IO;

cs int P=10000007;
int mu[P],prime[P],pcnt;
bool mark[P];
ll sum[P];

inline void linear_sieves(int len=P-7){
	mu[1]=1;
	for(int re i=2;i<=len;++i){
		if(!mark[i])mu[i]=-1,prime[++pcnt]=i,sum[i]=1;
		for(int re j=1;i*prime[j]<=len;++j){
			mark[i*prime[j]]=true;
			if(i%prime[j]==0){sum[i*prime[j]]=mu[i];break;}
			mu[i*prime[j]]=-mu[i];
			sum[i*prime[j]]=mu[i]-sum[i];
		}
	}
	for(int re i=1;i<=len;++i)sum[i]+=sum[i-1];
}

inline ll solve(int n,int m){
	if(n>m)swap(n,m);
	ll ans=0;
	for(int re i=1,j;i<=n;i=j+1){
		j=min(n/(n/i),m/(m/i));
		ans+=(ll)(n/i)*(m/i)*(sum[j]-sum[i-1]);
	}
	return ans;
}

signed main(){
	linear_sieves();
	for(int re T=getint();T--;pc('\n'))outint(solve(getint(),getint()));
	return 0;
}