bzoj 3309 DZY Loves Math —— 莫比乌斯反演+数论分块

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3309

凭着上课所讲和与 Narh 讨论推出式子来；

竟然是第一次写数论分块！所以迷惑了半天；

在预处理的筛中也犯了愚蠢的错误...总之全仰仗 Narh 提点了...

所以具体题解就看这里咯：https://www.cnblogs.com/Narh/p/9740786.html

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=1e7+;

int T,a[xn],b[xn],c[xn],tot,pri[xn],cnt;

ll s[xn];

bool vis[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

void init()

{

  int mx=1e7;

  for(int i=;i<=mx;i++)

    {

      if(!vis[i])a[i]=b[i]=c[i]=,pri[++cnt]=i;

      if(a[i]==)s[i]=s[i-]+((c[i]&)?:-); else s[i]=s[i-];

      for(int j=,k;j<=cnt&&(ll)i*pri[j]<=mx;j++)

    {

      vis[k=i*pri[j]]=;

      if(i%pri[j])//新增pri[j]

        {

          if(!a[i]||(a[i]&&b[i]!=))a[k]=,b[k]=;

          else a[k]=,b[k]=;

          c[k]=c[i]+;

        }

      else

        {

          int w=k,t=;

          while(w%pri[j]==)w/=pri[j],t++;

          if(w==||(a[w]&&b[w]==t))a[k]=,b[k]=t;

          else a[k]=,b[k]=;

          c[k]=c[i];

        }

    }

    }

}

int main()

{

  T=rd(); init();

  while(T--)

    {

      int n,m; n=rd(); m=rd();

      ll ans=;

      if(n>m)swap(n,m);

      for(int i=,nxt;i<=n;i=nxt+)

        ans+=(ll)(n/i)*(m/i)*(s[nxt=min(n/(n/i),m/(m/i))]-s[i-]);

      printf("%lld\n",ans);

    }

  return ;

}