给出一个长度为(n)的正整数序列(a)，(m)次询问(l,r,x)，问(max{i|iin[l,r],gcd(a_i,x)=1})。
(n,m,a_ile 10^5)。
分析
这个题很妙啊。
二分答案，问题变成判断在一个区间([l,r])中是否存在(gcd(a_i,x)=1)，变成判断([l,r])中有多少个(gcd(a_i,x) e 1)，我们要计算的就是：
[egin{aligned}
ret&=sum _{i=L}^R[gcd(a_i,x)
e 1] \
&=left[sum _{i=L}^Rsum _{d|x,d|a_i}mu (d)
ight]=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
",ans);
}
return 0;
}