题目链接

题解

莫比乌斯反演

∑i=1n∑j=1mf(gcd⁡(i,j))=∑T=1min⁡(n,m)⌊nT⌋⌊mT⌋∑d∣Tμ(Td)f(d) \begin{aligned} & \sum_{i=1}^n \sum_{j=1}^m f(\gcd(i,j))\\ = & \sum_{T=1}^{\min(n,m)}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}\mu(\frac{T}{d})f(d) \end{aligned} =​i=1∑n​j=1∑m​f(gcd(i,j))T=1∑min(n,m)​⌊Tn​⌋⌊Tm​⌋d∣T∑​μ(dT​)f(d)​

发现后面可以线筛，记录$low$代表最小的质因子的次数，$num$代表除了最小质因子以外的数是多少，由于每个数只会被最小质因子筛一次，因此上面两个可以很方便的求出。

记

g(T)=∑d∣Tμ(Td)f(d) g(T)=\sum_{d|T}\mu(\frac{T}{d})f(d) g(T)=d∣T∑​μ(dT​)f(d)

考虑

d=∏i=1kpiaiT=∏i=1kpibi d=\prod_{i=1}^k p_i^{a_i}\\ T=\prod_{i=1}^k p_i^{b_i} d=i=1∏k​piai​​T=i=1∏k​pibi​​

由于有一个莫比乌斯函数，因此∀i,bi−1≤ai≤bi\forall i,b_{i-1}\leq a_i\leq b_i∀i,bi−1​≤ai​≤bi​。

假设∃i,j,bj&lt;bi(i̸=j)\exists i,j,b_j&lt;b_i(i\not= j)∃i,j,bj​<bi​(i̸​=j)，那么对于aia_iai​无论是bib_ibi​还是bi−1b_i-1bi​−1，对$f$值没有任何影响，而对$\mu$值是$-1$和$1$的区别，因此此时$g(T)=0$。

否则，存在一个特殊情况

d=∏i=1kpibi−1 d=\prod_{i=1}^k p_i^{b_i-1} d=i=1∏k​pibi​−1​

此时μ(Td)f(d)=(−1)k(b−1)\mu(\frac{T}{d})f(d)=(-1)^k(b-1)μ(dT​)f(d)=(−1)k(b−1)，而对应的情况是μ(Td′)f(d′)=(−1)k−1b\mu(\frac{T}{d&#x27;})f(d&#x27;)=(-1)^{k-1}bμ(d′T​)f(d′)=(−1)k−1b，因此

g(T)=(−1)k+1 g(T)=(-1)^{k+1} g(T)=(−1)k+1

这个可以通过$num$数组实现转移。

代码

#include 
    
     #include 
     
      int read(){
      int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
          if(ch=='-')        {
              f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
          x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=10000000;int p[maxn+10],prime[maxn+10],cnt,low[maxn+10],num[maxn+10],f[maxn+10];int getprime(){
      p[1]=num[1]=1;  low[1]=f[1]=0;  for(int i=2; i<=maxn; ++i)    {
          if(!p[i])        {
              prime[++cnt]=i;          low[i]=num[i]=f[i]=1;        }      for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)        {
              int x=i*prime[j];          p[x]=1;          if(i%prime[j]==0)            {
                  low[x]=low[i]+1;              num[x]=num[i];              if(num[x]==1)                {
                      f[x]=1;                }              else                {
                      f[x]=(low[x]==low[num[x]])?-f[num[x]]:0;                }              break;            }          low[x]=1;          num[x]=i;          f[x]=(low[x]==low[i])?-f[i]:0;        }    }  for(int i=2; i<=maxn; ++i)    {
          f[i]+=f[i-1];    }  return 0;}int T,n,m;int main(){
      getprime();  T=read();  while(T--)    {
          n=read();      m=read();      long long ans=0;      for(int l=1,r; l<=std::min(n,m); l=r+1)        {
              r=std::min(n/(n/l),m/(m/l));          ans+=1ll*(f[r]-f[l-1])*(n/l)*(m/l);        }      printf("%lld\n",ans);    }  return 0;}