Submission #3391836

---

Source Code Expand

#include <iostream>
#include <unordered_map>
#include <vector>
#include <math.h>
#define llint long long
#define mod 1000000007
#define inf 1e18

using namespace std;
typedef unordered_map<llint, llint> UMP;

llint N, Q;
llint x[100005];
llint prime[100005];
UMP mp[100005];
UMP blk[1005];

int main(void)
{
	for(int i = 2; i < 1005; i++){
		if(prime[i]) continue;
		for(int j = 2*i; j < 100005; j+=i) prime[j] = i;
	}
	for(int i = 2; i < 100005; i++){
		llint x = i;
		while(prime[x]){
			mp[i][prime[x]]++;
			x /= prime[x];
		}
		if(x > 1) mp[i][x]++;
	}
	
	cin >> N >> Q;
	for(int i = 0; i < N; i++) cin >> x[i];
	
	llint B = sqrt(N), Bnum = (N+B-1)/B;
	for(int i = 0; i < N; i++){
		for(auto it = mp[x[i]].begin(); it != mp[x[i]].end(); it++){
			blk[i/B][it->first] += it->second;
		}
	}
	
	/*for(int i = 0; i < Bnum; i++){
		cout << blk[i].size() << endl;
	}*/
	
	llint l, r;
	for(int q = 0; q < Q; q++){
		cin >> l >> r;
		l--, r--;
		UMP tmp;
		llint ll = (l+B-1)/B*B, rr = r/B*B;
		//cout << ll << rr << endl;
		if(ll <= rr){
			for(int i = ll/B; i < rr/B; i++){
				for(auto it = blk[i].begin(); it != blk[i].end(); it++){
					tmp[it->first] += it->second;
				}
			}
			for(int i = l; i < ll; i++){
				for(auto it = mp[x[i]].begin(); it != mp[x[i]].end(); it++){
					tmp[it->first] += it->second;
				}
			}
			for(int i = rr; i < min(N, r+1); i++){
				for(auto it = mp[x[i]].begin(); it != mp[x[i]].end(); it++){
					tmp[it->first] += it->second;
				}
			}
		}
		else{
			for(int i = l; i <= r; i++){
				for(auto it = mp[x[i]].begin(); it != mp[x[i]].end(); it++){
					tmp[it->first] += it->second;
				}
			}
		}
		llint ans = 1;
		for(auto it = tmp.begin(); it != tmp.end(); it++){
			ans *= it->second + 1;
			ans %= mod;
		}
		cout << ans << endl;
	}
	
	return 0;
}

Submission Info

Judge Result