[CF594D] REQ 题解
思路
用欧拉函数的公式来求解，可以发现，对于每一个质因数都只会做一次贡献，然后是区间查询，联想到 HH的项链 一题，考虑离线询问，按右端点排序，在树状数组里面维护最靠右的质因数的位置做贡献，然后区间积一下就有了。
注意质因数分解暴力做根号应该会爆，可以筛质数之后对质数质因数分解，时间复杂度大约：\(O(\sqrt{\dfrac{n}{\ln n}})\)，跑得飞快。
总时间复杂度：\(O(nO(\sqrt{\dfrac{n}{\ln n}})\log p)\)。
另一种复杂度好看一点的的做法是线性筛最小质因数，然后每次除最小质因数，大约是 \(O(\log n)\) 的。
// Problem: REQ
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2024-01-03 21:59:43
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
// #define int long long
#define l first
#define r second
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 2e5 + 10, M = 1e6 + 10, mod = 1e9 + 7;
int n, a[N], Q;
pair<PII, int> q[N];
bool st[M];
int primes[M], tot, lowp[M];
void sieve(int n) {
for (int i = 2; i <= n; i ++) {
if(!st[i]) primes[++ tot] = i, lowp[i] = i;
for(int j = 1; primes[j] * i <= n && j <= tot; j ++) {
st[primes[j] * i] = true, lowp[i * primes[j]] = primes[j];
if(i % primes[j] == 0) break;
}
}
}
vector<int> dv;
void get_p(int a) {
while(a > 1) {
dv.push_back(lowp[a]);
a /= lowp[a];
}
dv.erase(unique(dv.begin(), dv.end()), dv.end());
}
int s[N];
struct BIT {
int tr[N];
void update(int i, int c) {i ++; for (; i <= n + 1; i += i & -i) tr[i] = 1ll * c * tr[i] % mod; }
int query(int i) {i ++; int res = 1; for (; i; i &= i - 1) res = 1ll * res * tr[i] % mod; return res; }
void clear() {for(int i = 1; i <= n + 1; i ++) tr[i] = 1;}
} bit;
int qmi(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = 1ll * res * a % mod;
b >>= 1, a = 1ll * a * a % mod;
}
return res;
}
int lst[M], ans[N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
sieve(M - 10), s[0] = 1;
cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i], s[i] = 1ll * s[i - 1] * a[i] % mod;
cin >> Q; for(int i = 1; i <= Q; i ++) cin >> q[i].l.l >> q[i].l.r, q[i].r = i;
sort(q + 1, q + Q + 1, [](pair<PII, int> a, pair<PII, int> b) {
return (a.l.r == b.l.r ? (a.l.l > b.l.l) : (a.l.r < b.l.r));
});
bit.clear();
for(int i = 1, now = 0; i <= Q; i ++) {
while(now < q[i].l.r) {
now ++, dv.clear(), get_p(a[now]);
for(auto p : dv) {
if(lst[p]) bit.update(lst[p], 1ll * p * qmi(p - 1, mod - 2) % mod);
bit.update(lst[p] = now, 1ll * (p - 1) * qmi(p, mod - 2) % mod);
}
}
ans[q[i].r] = 1ll * s[q[i].l.r] * qmi(s[q[i].l.l - 1], mod - 2) % mod * bit.query(q[i].l.r) % mod * qmi(bit.query(q[i].l.l - 1), mod - 2) % mod;
}
for(int i = 1; i <= Q; i ++)
cout << ans[i] << '\n';
return 0;
}