Submission #3791534

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
namespace Fact{
	long f[4000000];
	long rf[4000000];
	long pow(long N,long K){
		if(K == 0){
			return 1;
		}
		else if(K % 2 == 0){
			long t = pow(N,K/2);
			return t*t%mod;
		}
		else{
			return N*pow(N,K-1)%mod;
		}
	}
	void Fact(int N){
		for(int i=0;i<N+1;i++){
			if(i == 0){
				f[i] = 1;
			}
			else{
				f[i] = (f[i-1]*i)%mod;
			}
		}
		for(int i=N;i>=0;i--){
			if(i == N){
				rf[i] = pow(f[N],mod-2);
			}
			else{
				rf[i] = rf[i+1]*(i+1)%mod;
			}
		}
	}
	long GetFact(int N){
		return f[N];
	}
	long GetPerm(int N,int R){
		return f[N] * rf[N-R] % mod;
	}
	long GetConv(int N,int R){
		return ((f[N]*rf[R])%mod*rf[N-R])%mod;
	}
	long GetRev(int N){
		return rf[N] * f[N-1] % mod;
	}
}
int X[100000];
long ans[100000];
int L[100000];
int R[100000];
vector<int> prime;
int LowestPrimeFactor[100001];
int order[100000];
int pn[100000];
long c;
void Plus(int x){
	while(x != 1){
		int p = LowestPrimeFactor[x];
		c *= pn[p]+2;
		c %= mod;
		c *= Fact::GetRev(pn[p]+1);
		c %= mod;
		pn[p]++;
		x /= p;
	}
}
void Minus(int x){
	while(x != 1){
		int p = LowestPrimeFactor[x];
		c *= pn[p];
		c %= mod;
		c *= Fact::GetRev(pn[p]+1);
		c %= mod;
		pn[p]--;
		x /= p;
	}
}
bool compare(int x,int y){
	if(L[x] / 300 != L[y] / 300){
		return L[x] / 300 < L[y] / 300;
	}
	return R[x] < R[y];
}
void Calc(){
	int N = rei();
	int Q = rei();
	Fact::Fact(3600000);
	for(int i=0;i<N;i++){
		X[i] = rei();
	}
	for(int i=0;i<Q;i++){
		L[i] = rei()-1;
		R[i] = rei()-1;
		order[i] = i;
		ans[i] = 1;
	}
	for(int i=2;i<=100000;i++){
		if(LowestPrimeFactor[i] == 0){
			LowestPrimeFactor[i] = i;
			prime.push_back(i);
		}
		for(int j=0;j!=prime.size() && prime[j]<=LowestPrimeFactor[i];j++){
			if(i*prime[j] > 100000){
				break;
			}
			LowestPrimeFactor[i*prime[j]] = prime[j];
		}
	}
	for(int p=0;prime[p]<400;p++){
		for(int i=0;i<N;i++){
			while(LowestPrimeFactor[X[i]] == prime[p]){
				pn[i]++;
				X[i] /= prime[p];
			}
		}
		for(int i=1;i<N;i++){
			pn[i] += pn[i-1];
		}
		for(int q=0;q<Q;q++){
			ans[q] *= pn[R[q]] - (L[q] == 0 ? 0 : pn[L[q]-1]) + 1;
			ans[q] %= mod;
		}
		for(int i=0;i<N;i++){
			pn[i] = 0;
		}
	}
	sort(order,order+Q,compare);
	int l = 0;
	int r = -1;
	c = 1;
	for(int q=0;q<Q;q++){
		while(r < R[order[q]]){
			Plus(X[++r]);
		}
		while(l > L[order[q]]){
			Plus(X[--l]);
		}
		while(r > R[order[q]]){
			Minus(X[r--]);
		}
		while(l < L[order[q]]){
			Minus(X[l++]);
		}
		ans[order[q]] *= c;
	}
	for(int q=0;q<Q;q++){
		cout << ans[q]%mod << endl;
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Submission Info

Judge Result