Description

原题链接

​ 给定一长度为\(~n~\)的正整数序列\(~a~\)，有\(~q~\)次询问，每次询问一段区间内所有数的\(~LCM~\)(即最小公倍数)。由于答案可能很大，输出答案模\(~1e9 + 7~\)。\(~1 \leq n \leq 10 ^ 5~\),\(~1 \leq a_i \leq 10 ^ 9~\).

Solution

​ 看到这个题，第一感觉就是\(~O(n ^ 3)~\)暴力求\(~LCM~\)，可是发现这有个模数，扫一遍求\(~LCM~\)不现实。但的确我们可以从这个模数下手，来推到导\(~LCM~\)的一些性质。首先，对于一段数的\(~LCM~\)，不难发现就是其分解质因数后不同因子出现的最大幂次的乘积。对于序列中的每一个数\(~x~\)都可以分解成\(~x = \prod p_i ^ {k_i}~\)，可以把每一个\(~p_i ^ {k_ i}~\)都想象成为\(~k_i~\)个物品\(~p_{i,1}, ~p_{i,2}, ..., p_{i,{k_i}}~\)，每个物品的权值为\(~p_i~\)，原问题求得是相同\(~p_i~\)的最高次幂是多少，这个求区间不同物品的权值之和，不难发现这是等价的。

​ 考虑离线，把询问按右端点从小到大排序，每一次处理出右端点为\(~i~\)的答案，对于\(~i~\)的所有物品，都在树状数组的\(~i~\)位置乘上这个权值，在这个物品上一次出现的位置除以这个权值，再对右端点为\(~i~\)的询问更新即可。这个巧妙的求区间不同的元素个数的离线套路好像很经典。

Code

#include<bits/stdc++.h>

#define For(i, j, k) for(int i = j; i <= k; ++i)

#define Forr(i, j, k) for(int i = j; i >= k; --i)

using namespace std;

inline int read() {

	int x = 0, p = 1; char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') p = -1;

	for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

	return x *= p;

}

inline void File() {

    freopen("A1339.in", "r", stdin);

    freopen("A1339.out", "w", stdout);

}

typedef long long ll;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n, q, a[N], prime[N], isnot[N], cnt, ans[N], inv[N];

struct node { int l, r, id; } Q[N];

unordered_map<int, int> las;

inline bool cmp(const node &a, const node &b) { return a.r < b.r; }

inline void Init(int n) {

    isnot[1] = 1;

    For(i, 2, n) {

        if (!isnot[i]) prime[++ cnt] = i;

        For(j, 1, cnt) {

            if (1ll * i * prime[j] > n) break;

            isnot[i * prime[j]] = 1;

            if (i % prime[j] == 0) break;

        }

    }

}

inline int qpow(int a, int b) {

    static int res;

    for (res = 1; b; a = 1ll * a * a % mod, b >>= 1)

        if (b & 1) res = 1ll * a * res % mod;

    return res;

}

struct BIT {

	int c[N];

	inline void mul(int x, int v) {

        for (; x <= n; x += x & -x) c[x] = 1ll * c[x] * v % mod;

    }   

	inline int query(int x) {

        int res = 1;

        for (; x; x -= x & -x) res = 1ll * res * c[x] % mod;

        return res;

    }

} T;

int main() {

	File(), Init(31630);

	n = read(), q = read();

    For(i, 1, n) a[i] = read(), T.c[i] = 1;

    For(i, 1, q) Q[i].l = read(), Q[i].r = read(), Q[i].id = i;

    sort(Q + 1, Q + 1 + q, cmp);

	For(i, 1, cnt) inv[i] = qpow(prime[i], mod - 2);

	for (int i = 1, l = 1; i <= n; ++ i) {

		int tmp = a[i];

        for (int j = 1; prime[j] <= tmp && j <= cnt; ++ j) {

            if (tmp % prime[j] != 0) continue;

            for (int k = prime[j], lst; tmp % prime[j] == 0; k *= prime[j], tmp /= prime[j]) {

                T.mul(i, prime[j]), lst = las[k];

                if (lst) T.mul(lst, inv[j]);

                las[k] = i;

            }

        }

        if (tmp > 1) {

            T.mul(i, tmp); int lst = las[tmp];

            if (lst) T.mul(lst, qpow(tmp, mod - 2));

            las[tmp] = i;

        }

        int res = T.query(i);

        while (l <= q && Q[l].r == i) ans[Q[l].id] = 1ll * res * qpow(T.query(Q[l].l - 1), mod - 2) % mod, ++ l;

    }   

    For(i, 1, q) printf("%d\n", ans[i]);

    return 0;

}