---
# System prepended metadata

title: Untitled

---

Bài này có khá nhiều cách giải, tuy nhiên các bạn có thể tham khảo cách giải sau đây.

Ta sẽ xử lí offline bài toán này. Với mỗi truy vấn $i$ có dạng $[l,r]$, ta đẩy nó vào một vector $q_r$. 

Ta sẽ đi từ 1 cho tới n, với mỗi vị trí $i$, ta sẽ:
- Phân tích thừa số nguyên tố của $a_i$, với mỗi thừa số, ta gọi nó là $x$, $t$ là số mũ của thừa số nguyên tố đó.
- Với công thức tính $phi(n)$ của bài [này](https://hnoj.edu.vn/problem/phi), ta nhận thấy, ta sẽ nhân kết quả của đoạn $[1,i]$ với $(x^y*(x-1)$, với $y = t-1$ (do số $x$ đã bị chia một lần dưới mẫu. Tuy nhiên, trong trường hợp thừa số nguyên tố này đã xuất hiện và được ta nhân vào thời điểm $last[x]$, vậy thì việc ta nhân thêm $(x-1)/x$ sẽ bị thừa ra một lần trong khoảng $[1,last[x]]$, vậy nên ta cần nhân thêm $x/(x-1)$ vào đoạn này. Tất nhiên cần dùng tới kĩ thuật nghịch đảo module. Sau khi xong các truy vấn cập nhật, ta gán $last[x] = i$.
- Với mỗi truy vấn $[l,r]$ khi $i$ tiến tới r, kết quả của truy vấn sẽ là $get(l)$ (ta có thể dùng Segment Tree hoặc Fenwick Tree cho các thao tác get và cập nhật).

Code:
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N = 2e5+5;
const int M = 1e6+5;
int a[N];
int p[M];
void sieve (){
    for (int i=1; i<M; i++) p[i] = i;
    for (int i=2; i*i < M; i++){
        if (p[i] == i) for (int j= i*i; j< M; j+=i) p[j] = i;
    }
}
struct qr {
    int x,y;
};
vector<qr> q[N];
int bit[N];
const int mod = 1e9+7;
void update (int n, int val) {
    while (n>0) bit[n] *= val, bit[n]%=mod, n-=n&(-n);
}
int get (int x) {
    int ans = 1;
    while (x<=n) ans = ans*bit[x]%mod, x+=x&(-x);
    return ans;
}
int lst[M];
int cdt (int a, int b) {
    if (b == 0) return 1;
    int t = cdt(a,b/2);
    return (b%2 ? t*t%mod*a%mod : t*t%mod);
}
int res[N];
signed main(){
    sieve();
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i], bit[i] = 1;
    int m; cin >> m;
    for (int i=1; i<=m; i++) {
        int l,r; cin >> l >> r;
        q[r].push_back({l,i});
    }
    for (int i=1; i<=n; i++) {

        while (a[i]!=1) {
            int x = p [a[i]];
            int t = 0;
            while (a[i]%x == 0 ) a[i]/=x, t++;
            int tmp = cdt(x,t-1)*(x-1)%mod;
            update (i,tmp);
            int dak = cdt((x-1),mod-2)*x%mod;
            update (lst[x],dak);
            lst[x] = i;
        }
        for (int j=0; j<q[i].size(); j++) res[q[i][j].y] = get(q[i][j].x);
    }
    for (int i=1; i<=m; i++) cout << res[i] << '\n';
}
```