#include #include #include #include using namespace std; // Модулна константа const long long MOD = 1000000007; // Функция за бързо повдигане на степен (modular exponentiation) long long modexp(long long base, long long exp, long long mod = MOD) { long long res = 1 % mod; base %= mod; while (exp > 0) { if (exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; } // Функция за модулна инверсия (по Fermat, тъй като MOD е просто) long long modinv(long long a, long long mod = MOD) { return modexp(a, mod - 2, mod); } // Структура на Fenw (BIT), която поддържа точкови умножения и сумиране (на произведения) struct Fenw { int n; vector bit; Fenw(int n) : n(n) { bit.assign(n + 1, 1); } void update(int i, long long val) { for (; i <= n; i += i & -i) bit[i] = (bit[i] * val) % MOD; } long long query(int i) { long long res = 1; for (; i; i -= i & -i) res = (res * bit[i]) % MOD; return res; } long long range_query(int l, int r) { long long a = query(r); long long b = query(l - 1); return (a * modinv(b)) % MOD; } }; // Изчисляваме SPF (най-малък прост делител) за числа до max_n vector sieveSPF(int max_n) { vector spf(max_n + 1); for (int i = 1; i <= max_n; i++) spf[i] = i; for (int i = 2; i * i <= max_n; i++) { if (spf[i] == i) { for (int j = i * i; j <= max_n; j += i) { if (spf[j] == j) spf[j] = i; } } } return spf; } // Функция за разлагане на число на прости множители (взимаме само уникалните прости делители) vector factorizeDistinct(int x, const vector& spf) { vector res; while (x > 1) { int p = spf[x]; res.push_back(p); while (x % p == 0) x /= p; } return res; } // Главна функция int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // Отваряме входния и изходния файл ifstream fin("coprime.in"); ofstream fout("coprime.out"); int N, Q; fin >> N >> Q; vector arr(N + 1); for (int i = 1; i <= N; i++) { fin >> arr[i]; } // SPF до 10^6 (тъй като 1 ≤ a[i] ≤ 10^6) int maxVal = 1000000; vector spf = sieveSPF(maxVal); // За всяко a[i] намираме списък с неговите (различни) прости делители vector> factors(N + 1); for (int i = 1; i <= N; i++) { factors[i] = factorizeDistinct(arr[i], spf); } // Префиксно произведение: pref[i] = a1 * a2 * ... * ai (по модул MOD) vector prefix(N + 1, 1); for (int i = 1; i <= N; i++) { prefix[i] = (prefix[i - 1] * arr[i]) % MOD; } // Пресмятаме f(p) = (p-1)/p mod MOD за всички прости p vector f(maxVal + 1, 0); for (int p = 2; p <= maxVal; p++) { if (spf[p] == p) { // ако p е просто f[p] = ((long long)p - 1) * modinv(p) % MOD; } } // Четем заявките. Ще ги съхраним във вид: (l, r, idx) struct Query { int l, r, idx; }; vector queries(Q); for (int i = 0; i < Q; i++) { int l, r; fin >> l >> r; queries[i] = { l, r, i }; } // Сортираме заявките според r sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) { return a.r < b.r; }); // Инициализираме Fenw дървото за произведения (от 1 до N) Fenw fenw(N); // lastOccurrence[p] ще пази последната позиция, където простото p се среща vector lastOccurrence(maxVal + 1, 0); // Отговаряме на заявките “offline” – обработваме индекса от 1 до N, а заявките с дадено r, // които са достигнати, отговаряме. vector ans(Q, 0); int qIdx = 0; for (int i = 1; i <= N; i++) { // За a[i] обновяваме за всеки прост делител for (int p : factors[i]) { if (lastOccurrence[p] != 0) { // Ако p вече се е срещало, "отстраняваме" приноса от старата позиция: long long invVal = modinv(f[p]); fenw.update(lastOccurrence[p], invVal); } // И добавяме приноса в текущата позиция: fenw.update(i, f[p]); lastOccurrence[p] = i; } // Обработваме заявките, които завършват в i while (qIdx < Q && queries[qIdx].r == i) { int L = queries[qIdx].l, R = queries[qIdx].r; // Получаваме произведението на a[j] от j=L до R: long long prodRange = prefix[R] * modinv(prefix[L - 1]) % MOD; // Получаваме произведението на приносите на простите, които "влизат" в интервала long long distinctProd = fenw.range_query(L, R); // Тогава: φ(∏ a[j]) = (∏ a[j]) * (∏_{p|n} (1-1/p)) long long phiVal = (prodRange * distinctProd) % MOD; ans[queries[qIdx].idx] = phiVal; qIdx++; } } for (int i = 0; i < Q; i++) { fout << ans[i] << "\n"; } fin.close(); fout.close(); return 0; }