H-Curious

H-Curious

多组。
给出n个值域为[1,m]的数放在a数组中
再给出k个询问，每个询问给出一个x问
$$\sum _{i=1}^n\sum _{j=1}^n[gcd(a[i],a[j])==x]$$
看了题解后发现，妙啊。但是我只想到了比较套路的解法。以下是我的解法，复杂度mlogm，而题解的是nlogn。
实际上如果我们用vis统计x在数组中出现的次数。询问就变成了
$$\sum _{i=1}^m\sum _{j=1}^m[gcd(i,j)==x]\ast vis[i]\ast vis[j]$$
这个东西用来莫比乌斯反演是不是特别熟悉了呢，下面开始推式子：
$$\sum _{i=1}^m\sum _{j=1}^m[gcd(i,j)==x]\ast vis[i]\ast vis[j]$$
$$=\sum _{i=1}^{m/x}\sum _{j=1}^{m/x}[gcd(i,j)==1]\ast vis[i\ast x]\ast vis[j\ast x]$$
$$=\sum _{i=1}^{m/x}\sum _{j=1}^{m/x}vis[i\ast x]\ast vis[j\ast x]\ast \sum _{d|gcd(i,j)}u[d]$$
$$=\sum _{d=1}^{m/x}u[d]\ast \sum _{i=1}^{m/(x\ast d)}\sum _{j=1}^{m/(x\ast d)}vis[i\ast x\ast d]\ast vis[j\ast x\ast d]$$
$$=\sum _{d=1}^{m/x}u[d]\ast (\sum _{i=1}^{m/(x\ast d)}vis[i\ast d\ast x]{)}^2$$
然后我们预处理T属于1到m中所有的${\sum }_{i=1}^{m/T}vis[i\ast T]{)}^2$

由无穷级数可得复杂度是mln（m）的

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>

#include<map>
#include<queue>
#include<set>
#include<list>
#include<bitset>
/*#include<bits/stdc++.h>*/
//#pragma GCC optimize(2)
using namespace std;
typedef long long LL;
const int maxn=1000555;
const LL INF=1e9+7;
const LL mod=1e9+7;
void outLL(LL x)
{
	if(x<0){x=~x+1;putchar('-');}
	if(x>9)outLL(x/10);
	putchar(char(x%10+'0'));
}
const double PI=acos(-1);
#define pii pair<LL,LL>
#define mp(x,y) make_pair(x,y)
#define sfi(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a) scanf("%lf",&a)
LL n,m,x,k,vis[maxn];
LL su[maxn],cnt=0,u[maxn],sumu[maxn];
bool vissu[maxn];
void init()
{
	u[1]=1;
	for(int i=2;i<=maxn;++i)
	{
		if(!vissu[i])
		{
			u[i]=-1;
			su[++cnt]=i;
		}
		for(int j=1;j<=cnt&&i*su[j]<maxn;++j)
		{
			vissu[i*su[j]]=1;
			if(i%su[j])
			{
				u[i*su[j]]=-u[i];
			}
			else
			{
				u[i*su[j]]=0;
				break;
			}
		}
	}
}
LL yu[maxn];
void gao()
{
	for(int T=1;T<=m;++T)
	{
		LL now=0;
		for(int i=1;i<=m/T;++i)
		{
			now+=vis[i*T];
		}
		yu[T]=now;
	}
}
void solve()
{
	LL ans=0;
	sfl(n);sfl(m);sfl(k);
	for(int i=0;i<=m;++i)vis[i]=0,yu[i]=0;
	for(int i=1;i<=n;++i)
	{
		LL kk;sfl(kk);
		vis[kk]++;
	}
	gao();
	while(k--)
	{
		sfl(x);ans=0;
		for(int d=1;d<=m/x;++d)
		{
			LL now=yu[x*d];
			if(u[d]==0)continue;
			ans+=u[d]*now*now;
		}
		printf("%lld\n",ans);
	}
}
int main()
{
	init();
	int _;sfl(_);
	while(_--)solve();
	return 0;
	
}