Trước hết ta có công thức tính nhanh hàm ~\phi~. Với ~V = p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}~ (~p_1, p_2, \ldots, p_k~ là các ước nguyên tố phân biệt của ~V~), ~\phi (V) = (p_1 - 1) p_1^{e_1 - 1} (p2 - 1) p_2^{e_2 - 1}\ldots (p_k - 1) p_k^{e_k - 1}~ ~\phi (V) = \Pi_{i=1}^{k} \frac{p_i - 1}{p_i} {p_i}^{e_i}~ ~\phi (V) = V \times \Pi_{i=1}^{k} \frac{p_i - 1}{p_i}~

Xét trường hợp ~M~ là số nguyên tố. Áp dụng công thức trên, với mỗi query tính ~\phi(\Pi_{i=l}^r i)~ ta có ~\phi (Pi_{i=l}^r i) = (\Pi_{i=l}^r i) (\Pi_{p \in P_{l, r}} \frac{p - 1}{p})~ với ~P_{l, r}~ là tập các số nguyên tố là ước của ít nhất một số trong khoảng từ ~l~ đến ~r~.

Để tính tích ~\Pi_{p \in P} \frac{p - 1}{p}~, ta có thể lưu các giá trị này trong một cây phân đoạn (segment tree) và duyệt các query ~(l, r)~ theo thứ tự ~r~ tăng dần. Khi ~r = r_0~, giá trị ở vị trí ~i~ trên cây phân đoạn là tích ~\Pi_{p | i \% p = 0, i + p > r_0} \frac{p - 1}{p}~. Khi đi từ ~r = r_0 - 1~ sang ~r = r_0~, với mỗi ước nguyên tố ~p~ của ~r_0~, ta nhân giá trị ở vị trí ~r_0~ trên cây phân đoạn với ~\frac{p - 1}{p}~ và chia giá trị ở ~r_0 - p~ cho ~\frac{p - 1}{p}~. Sau đó với mỗi query ~(l, r_0)~ ta chỉ cần tính tích đoạn ~(l, r_0)~ trên cây phân đoạn.

Với ~M~ không phải số nguyên tố, ta có thể tính riêng tích trên cho các số nguyên tố ~p~ là ước của ~M~, sao đó nhân với tích cho các số nguyên tố không phải ước của ~M~.

Ngoài ra để tránh chia phép chia cho ~\frac{p - 1}{p}~ module ~M~ (vì ~p - 1~ và ~M~ có thể không nguyên tố cùng nhau), với mỗi vị trí ~i~ trên cây phân đoạn ta có thể duy trì ~V^1_i = \Pi_{p | i \% p = 0, i + p > r_0} p~. Lưu ý rằng nếu biết ~\Pi_{p | i \% p = 0, i + p > r_0} p~ ta có thể tính được ~V^0_i = \Pi_{p | i \% p = 0, i + p > r_0} \frac{p - 1}{p}~, giá trị ở vị trí ~i~ trên cây phân đoạn. Vì vậy ta có thể tính trước ~V^1_i~ cho ~10^6~ giá trị có thể của ~V^0_i~. Trong quá trình duyệt, khi di chuyển từ ~r = r_0 - 1~ sang ~r = r_0~, ta chỉ cần nhân ~V^1_{r_0}~ với p và chia ~V^1_{r_0 - p}~ cho p, sau đó cập nhật ~V^0_{r_0}~ và ~V^0_{r_0 - p}~ trên cây phân đoạn.

Độ phức tạp ~O(10^6 * log(10^6) * log(log(10^6)) + Q * log(10^6))~ với ~Q~ là số query.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

// #define int long long

const int maxval = 1e6 + 6, maxq = 1e6 + 6; 

int q; 
int m; 
int phi_m; 
unordered_map<int, int> factors[maxval], factors_m; 
int pref_prod_common_factors_removed[maxval]; 

int qleft[maxq], qright[maxq]; 
vector<pair<int, int> > queries[maxval]; 

bool pre_calc_not_needed[maxval]; 
int precalced_value_0[maxval]; 
int precalced_value[maxval]; 
int cur_p_prod[maxval]; 
int it[maxval * 4 + 5]; 

int ans[maxq]; 

void put_it(int i, int l, int r, int p, int v) { 
    if(l > p || p > r) { 
        return; 
    }
    if(l == r) { 
        it[i] = v; 
        // cout << "putting: " << i << " " << l << " " << r << v << endl; 
    }
    else { 
        int mid = l + r >> 1; 
        put_it(i << 1, l, mid, p, v); 
        put_it(i << 1 | 1, mid + 1, r, p, v); 
        it[i] = 1ll * it[i << 1] * it[i << 1 | 1] % m; 
    }
}

int get_it(int i, int l, int r, int ll, int rr) { 
    int re; 
    if(l > rr || ll > r) { 
        re = 1; 
    }
    else if(ll <= l && r <= rr) { 
        re= it[i]; 
    }
    else { 
        int mid = (l + r) >> 1; 
        int v1 = get_it(i << 1, l, mid, ll, rr), v2 = get_it(i << 1 | 1, mid + 1, r, ll, rr); 
         re = 1ll * v1 * v2 % m; 
    }

    return re; 
}


int bp(int i, int j) { 
    int r = 1; 
    while(j) { 
        if(j & 1) { 
            r = 1ll * r * i % m; 
        }
        j >>= 1; 
        i = 1ll * i * i % m; 
    }
    return r; 
}

int count_prefix_power(int p, int r) { 
    int sum = 0; 
    while(r) { 
        r /= p; 
        sum += r; 
    }
    return sum; 
}


signed main() {
    for(int i = 2; i < maxval; i++) { 
      if(factors[i].size() == 0) { 
          for(int j = i; j < maxval; j += i) { 
              int t = j; 
              while(t % i == 0) { 
                    factors[j][i] += 1; 
                    t /= i; 
                }
          }

          if(1ll * i * i < maxval) { 
            for(int j = i * i; j < maxval; j += i * i) { 
                pre_calc_not_needed[j] = true; 
            }
          }
      }
  }

   cin >> m >> q; 

  for(int qi = 1; qi <= q; qi++) { 
       cin >> qleft[qi] >> qright[qi]; 
       queries[qright[qi]].emplace_back(qleft[qi], qi); 
   }


  int temp_m = m; 
  for(int p = 2; p * p <= m; p++) { 
      while(temp_m % p == 0) { 
          temp_m /= p; 
          factors_m[p]++; 
      }
  }
  if(temp_m > 1) { 
      factors_m[temp_m]++; 
  }

    phi_m = 1; 
  for(auto t: factors_m) { 
      phi_m = 1ll * phi_m * (t.first - 1) % m * bp(t.first, t.second - 1) % m; 
  }

//   cout << phi_m << endl; 


  pref_prod_common_factors_removed[0] = 1; 
  for(int i = 1; i < maxval; i++) { 
      int i_common_factors_removed = 1;
      for(auto t: factors[i]) { 
          if(factors_m.count(t.first)) continue; 
          i_common_factors_removed *= bp(t.first, t.second); 
      }
      pref_prod_common_factors_removed[i] = 1ll * pref_prod_common_factors_removed[i - 1] * i_common_factors_removed % m; 
  }

    for(int i = 1; i < maxval * 4 + 5; i++) it[i] = 1; 

    for(int i = 1; i < maxval; i++) { 
        if(factors[i].size() == 1) { 
            precalced_value_0[i] = 1ll * (i - 1) * bp(i, phi_m - 1) % m; 
        }
    }

  for(int i = 1; i < maxval; i++) { 
      if(pre_calc_not_needed[i]) continue; 

      precalced_value[i] = 1; 
      for(auto t: factors[i]) { 
          if(m % t.first == 0) continue; 
          precalced_value[i] = 1ll * precalced_value[i] * precalced_value_0[t.first] % m; 
      }
  }

    auto get_it_value = [&] (int i) -> int { 
        return precalced_value[cur_p_prod[i]]; 
    }; 

    for(int r = 1; r < maxval; r++) { 
        cur_p_prod[r] = 1;

        for(auto t: factors[r]) { 
            int p = t.first; 
            if(m % p == 0) continue; 
            cur_p_prod[r] *= p; 
            put_it(1, 1, maxval, r, get_it_value(r)); 
            if(r > p) { 
                cur_p_prod[r - p] /= p; 
                put_it(1, 1, maxval, r - p, get_it_value(r - p)); 
            }
        }

        for(auto t: queries[r]) { 
            int l = t.first, qi = t.second; 
            ans[qi] = 1ll * pref_prod_common_factors_removed[r] 
                * bp(pref_prod_common_factors_removed[l - 1], phi_m - 1) % m 
                * get_it(1, 1, maxval, l, r) % m; 

            for(auto tt: factors_m) { 
                int power = count_prefix_power(tt.first, r) - count_prefix_power(tt.first, l - 1); 
                if(power) { 
                    ans[qi] = 1ll * ans[qi] * (tt.first - 1) % m 
                        * bp(tt.first, power - 1) % m; 
                }
            }
        }
    }
    for(int qi = 1; qi <= q; qi++) { 
        cout << ans[qi] << endl; 
    }
}