思路：

$\Sigma_{i=1}^n\Sigma_{j=1}^mgcd(i,j)==p(p是素数)$

$\Sigma_{p是素数}^{p<=n}\Sigma_{i=1}^{\lfloor \frac{n}{p} \rfloor}\Sigma_{j=1}^{\lfloor \frac{m}{p} \rfloor}gcd(i,j)==1$

由$e=μ|1$可得$gcd(i,j)==1 等价于 \Sigma_{d|gcd(i,j)} μ(d)$

所以原式为

$\Sigma_{p是素数}^{p<=n}\Sigma_{i=1}^{\lfloor \frac{n}{p} \rfloor}\Sigma_{j=1}^{\lfloor \frac{m}{p}\rfloor}\Sigma_{d|gcd(i,j)}μ(d)$

$\Sigma_{p是素数}^{p<=n}\Sigma_{i=1}^{\lfloor \frac{n}{p} \rfloor}\Sigma_{j=1}^{\lfloor \frac{m}{p}\rfloor}\Sigma_{d|i且d|j}μ(d)$

$\Sigma_{p是素数}^{p<=n}\Sigma_{d=1}^{\frac{n}{p}}\lfloor{\frac{n}{pd}}\rfloor\lfloor{\frac{m}{pd}}\rfloor μ(d)$

设$k=pd$

$\Sigma_{k=1}^{min(n,m)}\lfloor{\frac{n}{k}}\rfloor\lfloor{\frac{m}{k}}\rfloor\Sigma_{p|k}μ(\frac{k}{p})$

 

设$g(x)=\Sigma_{p|k}μ(\frac{k}{p})$

可以预处理g(x)

怎么求g(x)呢

有两种方法

1.暴力枚举

枚举素数 p

用$μ(p)$更新$μ(i*p)(i*p<=max(n,m))$

这样素数有$n/logn$个

枚举i的均摊复杂度是$O(logn)$的

乘起来就是$O(n)$了

2.

线性筛

对于素数p g(p)=1（显然）

 

由于$μ(x)_{x的因子有平方项}=0$

所以$prime[j]|i$的时候$g(i*prime[j])$的结果就是$μ(i)$了

因为我们求的是$\Sigma_{p|k}μ(\frac{k}{p})$而且$μ(x)$是积性函数

那我们不妨设$i*prime[j]=k$

设$P$是包含$prime[j]$的所有素数 $p$是不包含$prime[j]$的所有素数

$\Sigma_{P|k}μ(\frac{k}{P})=\Sigma_{P|k}μ(\frac{i*prime[j]}{P})$

$=\Sigma(μ(\frac{i}{p})*μ(prime[j]))+μ\frac{(i*prime[j])}{prime[j]}$

$=μ(prime[j])*g[i]+μ(i)=-g[i]+μ(i)$

 

处理完了g(x)

原式就是这个样子的$\Sigma_{k=1}^{min(n,m)}\lfloor{\frac{n}{k}}\rfloor\lfloor{\frac{m}{k}}\rfloor g(k)$

对于g(k)搞个前缀和

$\lfloor{\frac{n}{k}}\rfloor\lfloor{\frac{m}{k}}\rfloor$这个东西可以分块

 

终于搞完了

喜闻乐见

吼吼

枚举素数的

//By SiriusRen#include 
     
      #include 
      
       using namespace std;const int maxn=10000005;#define int long longint cases,n,m,mu[maxn],p[maxn],sum[maxn],f[maxn],tot;long long ans;bool vis[maxn];signed main(){    mu[1]=1;    for(int i=2;i
       
        m)swap(n,m);        for(int i=1,j;i<=n;i=j+1){            j=min(n/(n/i),m/(m/i));            ans+=(f[j]-f[i-1])*(n/i)*(m/i);        }        printf("%lld\n",ans);    }}
       
      
     

这是线性筛的

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const int N=10000005;int T,prime[N],vis[N],mu[N],tot,n,m;ll f[N],ans;int main(){    mu[1]=1;    for(int i=2;i