// https://ideone.com/No6ksW #pragma GCC optimize("Ofast") #include #define endl '\n' using namespace std; void fileIO() { freopen("coprime.in", "r", stdin); freopen("coprime.out", "w", stdout); } void fastIO() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int MAXN=2e5+5; const int MAXQ=1e5+5; const int MAXV=1e6+5; const int MOD=1e9+7; const long long MOD5=5*MOD; const int B=650; inline int64_t gilbertOrder(int x, int y, int pow, int rotate) { if (pow == 0) { return 0; } int hpow = 1 << (pow-1); int seg = (x < hpow) ? ( (y < hpow) ? 0 : 3 ) : ( (y < hpow) ? 1 : 2 ); seg = (seg + rotate) & 3; const int rotateDelta[4] = {3, 0, 0, 1}; int nx = x & (x ^ hpow), ny = y & (y ^ hpow); int nrot = (rotate + rotateDelta[seg]) & 3; int64_t subSquareSize = int64_t(1) << (2*pow - 2); int64_t ans = seg * subSquareSize; int64_t add = gilbertOrder(nx, ny, pow-1, nrot); ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1); return ans; } struct Query { int l, r, num; int64_t ord; inline void calcOrder() { ord = gilbertOrder(l, r, 21, 0); } }; inline bool operator<(const Query &a, const Query &b) { return a.ord < b.ord; } int n,q; int a[MAXN]; int inva[MAXN]; int pref[MAXN]; int lp[MAXV]; Query qr[MAXQ]; int bl[MAXN]; int t[MAXV]; int it[MAXV]; vector p[MAXN]; int cnt[MAXV]; long long cur=1; int ans[MAXQ]; int fastPow(int x,int pwr) { long long ret=1; while(pwr>0) { if(pwr&1) ret=ret*x%MOD; pwr/=2; x=1LL*x*x%MOD; } return ret; } int inv(int x) { return fastPow(x,MOD-2); } void sieve() { int mx=1e6; lp[1]=1; for(int i=2;i<=mx;i++) { if(!lp[i]) { lp[i]=i; t[i]=1LL*(i-1)*inv(i)%MOD; it[i]=inv(t[i]); if(1LL*i*i>mx) continue; for(int j=i*i;j<=mx;j+=i) { if(!lp[j]) lp[j]=i; } } } } inline void mult(int x) { cur*=x; if(cur>=MOD5) cur%=MOD; else while(cur>=MOD) cur-=MOD; } void add(int ind) { //cur=cur*a[ind]%MOD; for(auto x: p[ind]) { if(cnt[x]==0) mult(t[x]); //cur=cur*t[x]%MOD; cnt[x]++; } } void rem(int ind) { //cur=cur*inva[ind]%MOD; for(auto x: p[ind]) { if(cnt[x]==1) mult(it[x]); //cur=cur*it[x]%MOD; cnt[x]--; } } bool cmp(Query a, Query b) { if(bl[a.l]==bl[b.l]) { if(bl[a.l]%2==0) return a.lb.l; } else return bl[a.l]>n>>q; for(int i=1;i<=n;i++) { cin>>a[i]; //inva[i]=inv(a[i]); } sieve(); pref[0]=1; for(int i=1;i<=n;i++) pref[i]=1LL*pref[i-1]*a[i]%MOD; for(int i=1;i<=n;i++) { int x=a[i]; while(x>1) { if(p[i].empty()) p[i].push_back(lp[x]); else if(lp[x]!=p[i].back()) p[i].push_back(lp[x]); x/=lp[x]; } } //for(int i=1;i<=n;i++) bl[i]=i/B; for(int i=0;i>qr[i].l>>qr[i].r; qr[i].num=i; qr[i].calcOrder(); } sort(qr,qr+q); int l=1,r=0; for(int i=0;i