题意：

有5000组询问，每组询问求有多少i,j满足i∈[1,n]，j∈[1,m]且gcd(i,j)的质因子数目<=p。 n,m<=500000

思路：

首先预处理出每个数的质因子数目分别等于多少，则问题转化为求给定区间内，gcd等于某一堆数的i,j有多少组

发现很像一个基础莫比乌斯反演题：hdu1695。但是此题在某组询问中可能要处理很多个gcd，所以需要进行一些预处理

我们首先筛出每个数的莫比乌斯函数和它的质因子个数

通过容斥的公式可以看出如果要求的gcd为d，那么d*i的倍数对答案的贡献为 mobi[i]。

这样就可以预处理出每个p对应位置的莫比乌斯函数系数之和p[19][500000]

注意这里容易想到p是小于等于18的，因为50W之内的数最多有18个质因子(2^19>500000)

然后对p数组求前缀和，可以使单组查询复杂度变为p*sqrt(n)，具体为什么是分块sqrt(n)可以参考hdu1695的题解。交了一发超时了。。

还以为写搓了，后来发现可以再求一次前缀和。。这样单组查询变成了sqrt(n)，终于过了

代码：

1 #include 
      
        2 using namespace std; 3 const int maxn=500000; 4 int mb[maxn+10]; 5 int notprime[maxn+10]; 6 int num[maxn+10]; 7 int prime[maxn]; 8 vector
       
        v[20]; 9 int np=0;10 void setprime()11 {12     memset(notprime,0,sizeof(notprime));13     mb[1]=1;14     num[1]=0;15     for(int i=2; i<=maxn; i++)16     {17         if(!notprime[i])18         {19             prime[np++]=i;20             num[i]=1;21             mb[i]=-1;22         }23         for(int j=0; j
        
         <=maxn; j++)24         {25             notprime[i*prime[j]]=1;26             num[i*prime[j]]=num[i]+1;27             //v[num[i]+1].push_back(i*prime[j]);28             if(i%prime[j]==0)29             {30                 mb[i*prime[j]]=0;31                 break;32             }33             else34             {35                 mb[i*prime[j]]=-mb[i];36             }37         }38     }39 }40 int p[20][500050];41 int sum[20][500050];42 int f[20][500050];43 int main()44 {45     freopen("in.txt","r",stdin);46     setprime();47     for(int i=1; i<=maxn; i++)48     {49         for(int j=1; i*j<=maxn; j++)50         {51             p[num[i]][i*j]+=mb[j];52         }53     }54     for(int i=0; i<=18; i++)55     {56         sum[i][0]=0;57         for(int j=1; j<=maxn; j++)58         {59             sum[i][j]=sum[i][j-1]+p[i][j];60         }61     }62     for(int i=1; i<=maxn; i++)63     {64         f[0][i]=sum[0][i];65         for(int j=1;j<=18;j++)66         {67             f[j][i]=f[j-1][i]+sum[j][i];68         }69     }70     int n,m,k,q;71     scanf("%d",&q);72     while(q--)73     {74         long long ans=0;75         scanf("%d%d%d",&n,&m,&k);76         if(k>18)77         {78             printf("%I64d\n",(long long)n*m);79             continue;80         }81         if(n>m)82             swap(n,m);83         for(int j=1; j<=n; j++)84         {85             int to=min(n/(n/j),m/(m/j));86             ans+=(long long)(n/j)*(m/j)*(f[k][to]-f[k][j-1]);87             j=to;88         }89         printf("%I64d\n",ans);90     }91     return 0;92 }