# HackerEarth Mojtabas Array and Arpas Queries solution

In this HackerEarth Mojtabas Trees and Arpas Queries problem solution, Mojtba has an array a with n elements and an integer k. Arpa has q query in type [L,R], for i-th query print the length of the shortest segment [x,y] relate [Li,Ri], such that K | pi(y, j=x) aj.

## HackerEarth Mojtaba's Array and Arpa's Queries problem solution.

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 5e5 + 17, lg = 19;int n, k, q, fen[maxn], sp[lg][maxn], r[maxn], ans[maxn];vector<int> vec[maxn];void upd(int p, int x){    for(p++; p < maxn; p += p & -p)        fen[p] = min(x, fen[p]);}int get(int p){    int ans = maxn;    for(p++; p; p ^= p & -p)        ans = min(ans, fen[p]);    return ans;}int main(){    ios::sync_with_stdio(0), cin.tie(0);    memset(fen, 63, sizeof fen);    cin >> n >> k >> q;    for(int i = 0; i < n; i++){        cin >> sp[0][i];        sp[0][i] %= k;    }    for(int l = 1; l < lg; l++)        for(int i = 0; i + (1 << l) <= n; i++)            sp[l][i] = (ll) sp[l - 1][i] * sp[l - 1][i + (1 << l - 1)] % k;    for(int i = 0; i < q; i++){        int l;        cin >> l >> r[i];        r[i]--;        vec[l - 1].push_back(i);    }    for(int i = n - 1; i >= 0; i--){        int j = i, curz = 1; // catche some bug!        for(int lev = lg - 1; lev >= 0; lev--)            if(j + (1 << lev) < n && (ll) curz * sp[lev][j] % k){                curz = (ll) curz * sp[lev][j] % k;                j += 1 << lev;            }        if((ll) curz * sp[0][j] % k == 0)            upd(j, j - i + 1);        for(auto qi : vec[i])            ans[qi] = get(r[qi]);    }    for(int i = 0; i < q; i++)        cout << (ans[i] >= maxn ? -1 : ans[i]) << ' ';    cout << '\n';}`

### Second solution

`#include <bits/stdc++.h>#include <vector>#include <set>#include <map>#include <string>#include <cstdio>#include <cstdlib>#include <climits>#include <utility>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <iomanip>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp> using namespace std;using namespace __gnu_pbds;#define f(i,a,b) for(i=a;i<b;i++)#define rep(i,n) f(i,0,n)#define fd(i,a,b) for(i=a;i>=b;i--)#define pb push_back#define mp make_pair#define vi vector< int >#define vl vector< ll >#define ss second#define ff first#define ll long long#define pii pair< int,int >#define pll pair< ll,ll >#define sz(a) a.size()#define inf (1000*1000*1000+5)#define all(a) a.begin(),a.end()#define tri pair<int,pii>#define vii vector<pii>#define vll vector<pll>#define viii vector<tri>#define mod (1000*1000*1000+7)#define pqueue priority_queue< int >#define pdqueue priority_queue< int,vi ,greater< int > >#define flush fflush(stdout) #define primeDEN 727999983mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());// find_by_order()  // order_of_keytypedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;ll seg[2123456],segmul[2123456];ll a[512345];ll k;int build(int node,int s,int e){    seg[node]=inf;    if(s==e){        return 0;    }    int mid=(s+e)/2;    build(2*node,s,mid);    build(2*node+1,mid+1,e);    return 0;}int update(int node,int s,int e,int pos,int val){    if(s==e){        seg[node]=val;        return 0;    }    int mid=(s+e)/2;    if(pos<=mid)        update(2*node,s,mid,pos,val);    else        update(2*node+1,mid+1,e,pos,val);    seg[node]=min(seg[2*node],seg[2*node+1]);    return 0;}int query(int node,int s,int e,int l,int r){    if(e<l || r<s)        return inf;    if(l<=s && e<=r){        return seg[node];    }    int mid=(s+e)/2;    int ans=inf;    ans=min(ans,query(2*node,s,mid,l,r));    ans=min(ans,query(2*node+1,mid+1,e,l,r));    return ans;}vector<vi> gg(512345);vector<vii> quer(512345);int ans[512345],haha[512345];ll buildmul(int node,int s,int e){    if(s==e){        segmul[node]=a[s]%k;        return 0;    }    int mid=(s+e)/2;    buildmul(2*node,s,mid);    buildmul(2*node+1,mid+1,e);    segmul[node]=segmul[2*node]*segmul[2*node+1];    segmul[node]%=k;    return 0;}ll getans(int node,int s,int e,int l,int r){    if(e<l || r<s){        return 1;    }    if(l<=s && e<=r){    //cout<<node<<" "<<s<<" "<<e<<endl;        return segmul[node];    }    int mid=(s+e)/2;    ll ans=1;    ans*=getans(2*node,s,mid,l,r);    ans*=getans(2*node+1,mid+1,e,l,r);    ans%=k;    return ans;}int main(){    std::ios::sync_with_stdio(false); cin.tie(NULL);    int n,q;    cin>>n>>k>>q;    int i;    rep(i,n){        cin>>a[i];    }    buildmul(1,0,n-1);    build(1,0,n-1);    int j;    i=0;    j=0;    //cout<<getans(1,0,n-1,1,1)<<endl;    //return 0;    while(i<n && j<n){        if(j<i)            j=i;        if(getans(1,0,n-1,i,j)==0){            ans[i]=j;        //cout<<ans[i]-i+1<<endl;            gg[j].pb(i);            i++;        }        else{            j++;        }    }    int l,r;    rep(i,q){        cin>>l>>r;        l--;        r--;        quer[r].pb(mp(l,i));    }    //return 0;    rep(i,n){        rep(j,gg[i].size()){            update(1,0,n-1,gg[i][j],i-gg[i][j]+1);        }        rep(j,quer[i].size()){            haha[quer[i][j].ss]=query(1,0,n-1,quer[i][j].ff,i);        }    }    rep(i,q){        if(haha[i]==inf)            haha[i]=-1;        cout<<haha[i]<<" ";    }    cout<<endl;    return 0;   }`