Translation #

Given a sequence $a$ of length $n$ and $q$ queries in format $l,r,x$ , find $\max\limits_{l\leq i\leq r}\gcd(x,a_i)$ .

Solution #

Since $a_i$ is rather small, we can precalculate all the factors of all the numbers smaller than $1e5$ . Then, for each factor, we store all the $i$ such that $a_i$ contains this factor in ascending order.

For each query, we iterate all the factors from biggest to smallest and see if we can find some number in $[l,r]$ that contains this factor. We could use binary search to achieve this.

Code #

#include <bits/stdc++.h>
 
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define pb push_back
using namespace std;
 
const int N=1e5+5;
vector<int> p[N],fac[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n,q;
	cin>>n>>q;
	for1(i,1e5){
		for(int j=i;j<=1e5;j+=i) fac[j].pb(i);
	}
	for1(i,n){
		int x;
		cin>>x;
		for(auto f:fac[x]) p[f].pb(i);
	}
	while(q--){
		int l,r,x;
		cin>>l>>r>>x;
		for(int i=fac[x].size()-1;i>=0;i--){
			int f=fac[x][i];
			if(p[f].empty()) continue;
			auto it=lower_bound(p[f].begin(),p[f].end(),l);
			if(it!=p[f].end()&&*it<=r){
				cout<<f<<endl;
				break;
			}
		}
	}
    return 0;
}

Solution for NewCoder 4090E - 最大GCD(max GCD)

Translation #

Solution #

Code #