H-Curious

admin管理员组

文章数量:1612098

H-Curious

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

本文标签： curious