RT，$78 \operatorname{pts}$，大常数选手求助卡常 /kk

代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>

using namespace std;

const int N = 2 + 7;

typedef struct {
	int cnt = 0;
	int prime[N];
} Factorization;

typedef struct {
	int id;
	int l;
	int r;
} Query;

const int M = 1e3 + 7, K = 2e5 + 7, P = 1e5 + 7, Q = 3, R = 1 << 6, mod = 19260817;
int block, cur_ans = 1;
int prime[M], id[M], inv[K], a[P], sum[P][M], big_prime_bucket[K], big_prime_cnt[K], test_prime[Q + 7] = {0, 2, 7, 61}, ans[K];
bool p[M];
Factorization big_prime[P];
Query query[P];

bool operator <(const Query a, const Query b){
	if (a.l / block != b.l / block) return a.l < b.l;
	return a.r < b.r;
}

inline int init(int n){
	int cnt = 0;
	p[0] = p[1] = true;
	for (register int i = 2; i < M; ++i){
		if (!p[i]){
			cnt++;
			prime[cnt] = i;
			id[i] = cnt;
		}
		for (register int j = 1; j <= cnt && i * prime[j] < M; ++j){
			p[i * prime[j]] = true;
			if (i % prime[j] == 0) break;
		}
	}
	inv[0] = inv[1] = 1;
    for (register int i = 2; i <= n; ++i){
	    inv[i] = mod - 1ll * (mod / i) * inv[mod % i] % mod;
	}
	return cnt;
}

inline int quick_pow(int x, int p, int mod){
	int ans = 1;
	while (p){
		if (p & 1) ans = 1ll * ans * x % mod;
		x = 1ll * x * x % mod;
		p >>= 1;
	}
	return ans;
}

inline bool miller_rabin(int n, int k){
	int nd = n - 1, m = nd;
	while (m){
		int x = quick_pow(k, m, n);
		if (x != 1 && x != nd) return false;
		if ((m & 1) == 1 || x == nd) return true;
		m >>= 1;
	}
	return true;
}

inline bool is_prime(int n){
	if (n < 2) return false;
	for (register int i = 1; i <= Q; ++i){
		if (n == test_prime[i]) return true;
		if (!miller_rabin(n, test_prime[i])) return false;
	}
	return true;
}

inline int floyd(int a, int b, int p){
	return (1ll * a * a % p + b) % p;
}

int gcd(int a, int b){
	return b == 0 ? a : gcd(b, a % b);
}

inline int pollard_pho(int n){
	int x = 0, c = rand() % n;
	for (register int i = 1; ; i <<= 1){
		int y = 1, z = x, ans;
		for (register int j = 0; j < i; ++j){
			x = floyd(x, c, n);
			y = 1ll * y * abs(x - z) % n;
			if (j % R == 0){
				ans = gcd(n, y);
				if (ans > 1) return ans;
			}
		}
	}
}

inline void decompound(int n, Factorization &ans){
	if (n < 2) return;
	if (is_prime(n)){
		ans.prime[++ans.cnt] = n;
	} else {
		int factor;
		do {
			factor = pollard_pho(n);
		} while (factor == n);
		ans.prime[++ans.cnt] = factor;
		ans.prime[++ans.cnt] = n / factor;
	}
}

inline void add(int x){
	for (register int i = 1; i <= big_prime[x].cnt; ++i){
		cur_ans = 1ll * cur_ans * inv[big_prime_cnt[big_prime[x].prime[i]]] % mod * (++big_prime_cnt[big_prime[x].prime[i]]) % mod;
	}
}

inline void del(int x){
	for (register int i = 1; i <= big_prime[x].cnt; ++i){
		cur_ans = 1ll * cur_ans * inv[big_prime_cnt[big_prime[x].prime[i]]] % mod * (--big_prime_cnt[big_prime[x].prime[i]]) % mod;
	}
}

int main(){
	int n, m, cnt, bucket_cnt = 0;
	scanf("%d %d", &n, &m);
	block = ceil(n / sqrt(m));
	cnt = init(n * 2);
	srand(time(NULL));
	for (register int i = 1; i <= n; ++i){
		scanf("%d", &a[i]);
		for (register int j = 1; j <= cnt; ++j){
			sum[i][j] = sum[i - 1][j];
		}
		for (register int j = 1; j <= cnt; ++j){
			while (a[i] % prime[j] == 0){
				a[i] /= prime[j];
				sum[i][j]++;
			}
		}
		decompound(a[i], big_prime[i]);
	}
	for (register int i = 1; i <= n; ++i){
		for (register int j = 1; j <= big_prime[i].cnt; ++j){
			big_prime_bucket[++bucket_cnt] = big_prime[i].prime[j];
		}
	}
	sort(big_prime_bucket + 1, big_prime_bucket + bucket_cnt + 1);
	bucket_cnt = unique(big_prime_bucket + 1, big_prime_bucket + bucket_cnt + 1) - big_prime_bucket - 1;
	for (register int i = 1; i <= n; ++i){
		for (register int j = 1; j <= big_prime[i].cnt; ++j){
			big_prime[i].prime[j] = lower_bound(big_prime_bucket + 1, big_prime_bucket + bucket_cnt + 1, big_prime[i].prime[j]) - big_prime_bucket;
		}
	}
	for (register int i = 1; i <= bucket_cnt; ++i){
		big_prime_cnt[i] = 1;
	}
	for (register int i = 1; i <= m; ++i){
		scanf("%d %d", &query[i].l, &query[i].r);
		query[i].id = i;
	}
	sort(query + 1, query + m + 1);
	for (register int i = 1, j = 1, k = 0; i <= m; ++i){
		Query cur = query[i];
		while (j > cur.l) add(--j);
		while (k < cur.r) add(++k);
		while (j < cur.l) del(j++);
		while (k > cur.r) del(k--);
		ans[cur.id] = cur_ans;
		for (register int l = 1; l <= cnt; l++){
			ans[cur.id] = 1ll * ans[cur.id] * (sum[cur.r][l] - sum[cur.l - 1][l] + 1) % mod;
		}
	}
	for (register int i = 1; i <= m; ++i){
		printf("%d\n", ans[i]);
	}
	return 0;
}