ICPCCamp 2017 I Coprime Queries

给出一个长度为\(n\)的正整数序列\(a\)，\(m\)次询问\(l,r,x\)，问\(max\{i|i\in[l,r],gcd(a_i,x)=1\}\)。

\(n,m,a_i\le 10^5\)。

分析

这个题很妙啊。

二分答案，问题变成判断在一个区间\([l,r]\)中是否存在\(gcd(a_i,x)=1\)，变成判断\([l,r]\)中有多少个\(gcd(a_i,x)\ne 1\)，我们要计算的就是：

\[\begin{aligned}
ret&=\sum _{i=L}^R[gcd(a_i,x)\ne 1] \\
&=\left[\sum _{i=L}^R\sum _{d|x,d|a_i}\mu (d)\right]=0 \\
\end{aligned}
\]

这个怎么算呢？我们注意到，如果\(d\)含有平方因子，那么\(\mu (d)\)必定是0，不需要去计算，所以我们只需要统计无平方因子数。可以发现，对于\(10^5\)以内的数，它的无平方因子非常少，最多为64个（\(2*3*5*7*11*13*17>10^5\)），所以直接枚举就好了。对于\([1,10^5]\)内的所有无平方因子数，我们记录含有它的每个\(a_i\)的下标\(i\)，每次对于询问的\(x\)在区间内二分计算即可。

复杂度约为\(O(64nlog^2n)\)。

代码

#include<cstdio>

#include<cctype>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long giant;

int read() {

	int x=0,f=1;

	char c=getchar();

	for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;

	for (;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

const int maxn=1e5+1;

int a[maxn],pm[maxn],ps=0,mu[maxn],from[maxn];

int sf[maxn],id[maxn],fs=0;

bool np[maxn];

vector<int> vec[maxn],my[maxn];

int many(int l,int r,int d) {

	++r;

	int fx=lower_bound(vec[d].begin(),vec[d].end(),l)-vec[d].begin();

	int fy=lower_bound(vec[d].begin(),vec[d].end(),r)-vec[d].begin();

	return fy-fx;

}

bool ok(int l,int r,int x) {

	int ret=0;

	for (int d:my[x]) {

		int gs=many(l,r,d);

		ret+=mu[d]*gs;

	}

	return ret;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

	freopen("my.out","w",stdout);

#endif

	int n=read(),q=read();

	mu[1]=1;

	for (int i=2;i<maxn;++i) {

		if (!np[i]) pm[++ps]=i,mu[i]=-1,from[i]=1;

		for (int j=1;j<=ps && (giant)pm[j]*i<maxn;++j) {

			int tmp=pm[j]*i;

			from[tmp]=i;

			np[tmp]=true;

			if (i%pm[j]==0) {

				mu[tmp]=0;

				break;

			}

			mu[tmp]=-mu[i];

		}

	}

	for (int i=1;i<maxn;++i) if (mu[i]) sf[++fs]=i,id[i]=fs;

	for (int i=1;i<maxn;++i) {

		for (int j=1;(giant)j*j<=i;++j) if (i%j==0) {

			if (mu[j]) my[i].push_back(j);

			if ((giant)j*j!=i && mu[i/j]) my[i].push_back(i/j);

		}

	}

	for (int i=1;i<=n;++i) {

		int x=a[i]=read();

		for (int d:my[x]) vec[d].push_back(i);

	}

	while (q--) {

		int l=read(),r=read(),x=read(),mid,ans=-1;

		while (l<=r) {

			int mid=l+r>>1;

			if (ok(mid,r,x)) l=mid+1,ans=mid; else r=mid-1;

		}

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

	}

	return 0;

}

巴特西

ICPCCamp 2017 I Coprime Queries

分析

代码

最新文章

热门文章