题解 - [Luogu P7486] 「Stoi2031」彩虹

喜欢我 \(\prod_i\prod_j [i,j]^{[i,j]}\) 吗 😁

题目链接

原始题面

题目背景

你要离开 我知道很简单 你说依赖 是我们的阻碍 就算放开 那能不能别没收我的爱 就当我最后才明白 ——《彩虹》

题目描述

虹是一个喜欢幻想的女孩子。她认为两个正整数 \(i,j\) 的 依赖值 为 \(\operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)}\). 她定义所有满足 \(l \le i \le r,l \le j \le r\) 的 \(i,j\) 的 依赖值 之积为两个正整数 \(l,r\) 的 阻碍值. 现在她给了你一个正整数 \(n\), 并 \(t\) 次询问你两个满足 \(1 \le l \le r \le n\) 的正整数 \(l,r\) 的 阻碍值 \(ans\bmod{32465177}\)

输入格式

第一行两个正整数 \(t,n\)

接下来 \(t\) 行，每行两个正整数 \(l_i,r_i\), 表示一次询问

输出格式

对于每组询问输出一个整数表示答案

样例 #1

样例输入 #1

3 7
1 3
2 3
7 7

样例输出 #1

21072733
12145631
823543

提示

简述版题意

给定 \(l,r\), 求 \(\prod\limits_{i=l}^{r}\prod\limits_{j=l}^{r}\operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)} \bmod{32465177}\). 多次询问

样例解释

对于第 \(1\) 次询问，\(ans=1^1 \times (2^2)^3 \times (3^3)^3 \times (6^6)^2\), \(ans \bmod{32465177}=21072733\);

对于第 \(2\) 次询问，\(ans=2^2 \times 3^3 \times (6^6)^2\), \(ans \bmod{32465177}=12145631\);

对于第 \(3\) 次询问，\(ans=7^7=823543\)

数据范围

对于 \(30\%\) 的数据，\(1 \le n \le 10^3,t=1\);

对于 \(60\%\) 的数据，\(1 \le n \le 10^5,t=1\);

对于 \(100\%\) 的数据，\(1 \le n \le 10^6,1 \le t \le 10,1 \le l_i \le r_i \le n\)

解题思路

设

\[ S(n,m)=\prod_{i=1}^n\prod_{j=1}^m[i,j]^{[i,j]} \]

不妨设 \(n\leq m\), 所求即为

\[ \frac{S(r,r)S(l-1,l-1)}{S(l-1,r)^2} \]

推式子

\[ \begin{aligned} S(n,m)&=\prod_{i=1}^n\prod_{j=1}^m[i,j]^{[i,j]}\\ &=\prod_{i=1}^n\prod_{j=1}^m\left(\frac{ij}{(i,j)}\right)^{\frac{ij}{(i,j)}}\\ &=\prod_{d=1}^n\prod_{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor}(ijd)^{ijd[(i,j)=1]}\\ &=\prod_{d=1}^n\prod_{e=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{i=1}^{\lfloor\frac{n}{de}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{de}\rfloor}(ijde^2)^{ijde^2\mu(e)}\\ &\xlongequal{D=de}\prod_{D=1}^n\prod_{e\mid D}\prod_{i=1}^{\lfloor\frac{n}{D}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{D}\rfloor}(ijDe)^{ijDe\mu(e)} \end{aligned} \]

即

\[ S(n,m)=\prod_{d=1}^n\prod_{e\mid d}\prod_{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor}(ijde)^{ijde\mu(e)} \]

接着推

\[ \begin{aligned} S(n,m)&=\prod_{d=1}^n\prod_{e\mid d}\prod_{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor}(ijde)^{ijde\mu(e)}\\ &=\prod_{d=1}^n\prod_{e\mid d}\left(\prod_{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor}(ij)^{ij}\right)^{de\mu(e)}\prod_{d=1}^n\prod_{e\mid d}(de)^{de\mu(e)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij}\\ &\xlongequal[s(n)=\sum_{i=1}^n i=\frac{n(n+1)}{2}]{H(n)=\prod_{i=1}^n i^i}\prod_{d=1}^n\prod_{e\mid d}\left(H\left(\left\lfloor\frac{n}{d}\right\rfloor\right)^{s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}H\left(\left\lfloor\frac{m}{d}\right\rfloor\right)^{s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)}\right)^{de\mu(e)}\prod_{d=1}^n\prod_{e\mid d}(de)^{de\mu(e)s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\\ &\xlongequal[h(n)=(\{\operatorname{id}\mu\}*\{1\})(n)]{g(m,n)=H(n)^{s(m)}H(m)^{s(n)}}\prod_{d=1}^ng\left(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor\right)^{dh(d)}\prod_{d=1}^nd^{dh(d)s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\prod_{d=1}^n\prod_{e\mid d}e^{de\mu(e)s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\\ &\xlongequal{k(n)=\prod_{e\mid n}e^{e\mu(e)}}\prod_{d=1}^ng\left(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor\right)^{dh(d)}\prod_{d=1}^nd^{dh(d)s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\prod_{d=1}^nk(d)^{ds\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\\ &=\prod_{d=1}^n\left(g\left(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor\right)^{h(d)}\left(d^{h(d)}k(d)\right)^{s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)}\right)^{d}\\ &=\prod_{d=1}^ng\left(\left\lfloor\frac{n}{d}\right\rfloor,\left\lfloor\frac{m}{d}\right\rfloor\right)^{dh(d)}\prod_{d=1}^n\left(d^{dh(d)}k(d)^d\right)^{s\left(\left\lfloor\frac{n}{d}\right\rfloor\right)s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)} \end{aligned} \]

之后预处理一下后整除分块即可

时间复杂度

\(O(n\log n+t\sqrt{n}\log n)\)

代码参考

Show code

Luogu_P7486view raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
#include <bits/stdtr1c++.h>
#include <ext/algorithm>
#include <ext/rb_tree>
#include <ext/rope>
#include <ext/vstring.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
template <class Tp>
using vc = std::vector<Tp>;
namespace NdVector {
template <size_t N, class Tp>
struct ndvector: public std::vector<ndvector<N - 1, Tp>> {
  static_assert(N > 0, "N should be positive");
  using base_tp = ndvector<N - 1, Tp>;
  using base = std::vector<base_tp>;
  using self = ndvector<N, Tp>;
  template <class T, typename... Ts>
  ndvector(T &&n, Ts &&...args): base(n, base_tp(args...)) {}
  constexpr size_t dim() const { return N; }
  template <class T>
  void fill(T &&x) {
    for (auto &i : *this) i.fill(x);
  }
};
template <class Tp>
struct ndvector<1, Tp>: public std::vector<Tp> {
  using base = std::vector<Tp>;
  using self = ndvector<1, Tp>;
  template <class T>
  ndvector(T &&n): base(n) {}
  constexpr size_t dim() const { return 1; }
  template <class T>
  void fill(T &&x) {
    std::fill(this->begin(), this->end(), x);
  }
};
}  // namespace NdVector
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    std::enable_if_t<std::is_same<decltype(std::declval<Tp>().begin()),
                                  typename Tp::iterator>::value &&
                     std::is_same<decltype(std::declval<Tp>().end()),
                                  typename Tp::iterator>::value> * = nullptr>
  size_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
using u32 = uint32_t;
using i64 = int64_t;
#define for_(i, l, r, vars...)                                            \
  for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \
       i <= i##end;                                                       \
       ++i)
#define for_step_(i, l, r, s, vars...)                                    \
  for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \
       i <= i##end;                                                       \
       i += s)
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(Tp i) -> bool {
  return i && (i & -i) == i;
}
#define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple>>
namespace tuple_detail_ {
template <std::size_t Begin, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
apply2_impl_(BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) {
  return std::make_tuple(
    std::forward<BinOp>(f)(std::get<Is>(lhs), std::get<Is>(rhs))...);
}
}  // namespace tuple_detail_
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(Tuple &&t) {
  static_assert(Begin <= TPL_SIZE_(Tuple) && Len <= TPL_SIZE_(Tuple) &&
                  Begin + Len <= TPL_SIZE_(Tuple),
                "Out of range");
  return tuple_detail_::subtuple_impl_<Begin>(t,
                                              std::make_index_sequence<Len>());
}
template <std::size_t Pos, class Tp, class Tuple>
constexpr auto tuple_push(Tp &&v, Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        std::make_tuple(v),
                        subtuple<Pos, TPL_SIZE_(Tuple) - Pos>(t));
}
template <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_pop(Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        subtuple<Pos + 1, TPL_SIZE_(Tuple) - Pos - 1>(t));
}
template <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(BinOp &&f, Tuple &&lhs, Tuple &&rhs) {
  return tuple_detail_::apply2_impl_(
    f, lhs, rhs, std::make_index_sequence<TPL_SIZE_(Tuple)>());
}
#define OO_PTEQ_(op)                                                          \
  template <class Tp, class Up>                                               \
  constexpr auto operator op(std::pair<Tp, Up> lhs,                           \
                             const std::pair<Tp, Up> &rhs) {                  \
    return std::pair<Tp, Up>{lhs.first op rhs.first,                          \
                             lhs.second op rhs.second};                       \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op(std::tuple<Ts...> const &lhs,                    \
                             std::tuple<Ts...> const &rhs) {                  \
    return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs);       \
  }                                                                           \
  template <class Tp, class Up>                                               \
  constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs,         \
                                              const std::pair<Tp, Up> &rhs) { \
    lhs.first op## = rhs.first;                                               \
    lhs.second op## = rhs.second;                                             \
    return lhs;                                                               \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op##=(std::tuple<Ts...> &lhs,                       \
                                const std::tuple<Ts...> &rhs) {               \
    return lhs = lhs op rhs;                                                  \
  }
OO_PTEQ_(+)
OO_PTEQ_(-)
OO_PTEQ_(*)
OO_PTEQ_(/)
OO_PTEQ_(%)
OO_PTEQ_(&)
OO_PTEQ_(|)
OO_PTEQ_(^)
OO_PTEQ_(<<)
OO_PTEQ_(>>)
#undef OO_PTEQ_
#undef TPL_SIZE_
template <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
std::ostream &operator<<(std::ostream &os, const std::pair<Tp, Up> &p) {
  return os << p.first << ' ' << p.second;
}
template <typename... Ts>
std::istream &operator>>(std::istream &is, std::tuple<Ts...> &p) {
  std::apply([&](Ts &...targs) { ((is >> targs), ...); }, p);
  return is;
}
template <typename... Ts>
std::ostream &operator<<(std::ostream &os, const std::tuple<Ts...> &p) {
  std::apply(
    [&](Ts const &...targs) {
      std::size_t n{0};
      ((os << targs << (++n != sizeof...(Ts) ? " " : "")), ...);
    },
    p);
  return os;
}
template <
  class Ch,
  class Tr,
  class Ct,
  std::enable_if_t<std::is_same<decltype(std::declval<Ct>().begin()),
                                typename Ct::iterator>::value &&
                   std::is_same<decltype(std::declval<Ct>().end()),
                                typename Ct::iterator>::value> * = nullptr>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os,
                                       const Ct &x) {
  if (x.begin() == x.end()) return os;
  for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' ';
  os << x.back();
  return os;
}
const u32 OFFSET = 5;
const u32 N = 1e6 + OFFSET;
const i64 MOD = 32465177;
using namespace std;
namespace MODINT {
constexpr int64_t safe_mod(int64_t x, int64_t m) {
  return (x %= m) < 0 ? x + m : x;
}
constexpr std::pair<int64_t, int64_t> invgcd(int64_t a, int64_t b) {
  if ((a = safe_mod(a, b)) == 0) return {b, 0};
  int64_t s = b, m0 = 0;
  for (int64_t q = 0, _ = 0, m1 = 1; a;) {
    _ = s - a * (q = s / a);
    s = a;
    a = _;
    _ = m0 - m1 * q;
    m0 = m1;
    m1 = _;
  }
  return {s, m0 + (m0 < 0 ? b / s : 0)};
}
template <uint32_t MOD>
class Mint {
  static_assert(MOD >= 1);
  using self = Mint<MOD>;

protected:
  uint32_t v_;

public:
  constexpr static uint32_t mod() { return MOD; }
  constexpr static self raw(uint32_t v) {
    self x;
    x.v_ = v;
    return x;
  }
  constexpr Mint(): v_(0) {}
  template <class T,
            std::enable_if_t<std::is_integral<T>::value &&
                             std::is_signed<T>::value> * = nullptr>
  constexpr Mint(T v): Mint() {
    int64_t x = (int64_t)(v % (int64_t)mod());
    v_ = (uint32_t)(x + (x < 0 ? mod() : 0));
  }
  template <class T,
            std::enable_if_t<std::is_integral<T>::value &&
                             std::is_unsigned<T>::value> * = nullptr>
  constexpr Mint(T v): v_((uint32_t)(v % mod())) {}
  friend std::istream &operator>>(std::istream &is, self &x) {
    int64_t xx;
    is >> xx;
    xx %= mod();
    x.v_ = (uint32_t)(xx + (xx < 0 ? mod() : 0));
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const self &x) {
    return os << x.v_;
  }
  constexpr const uint32_t &val() const { return v_; }
  constexpr explicit operator uint32_t() const { return val(); }
  constexpr uint32_t &data() { return v_; }
  constexpr self &operator++() {
    if (++v_ == mod()) v_ = 0;
    return *this;
  }
  constexpr self &operator--() {
    if (!v_) v_ = mod();
    --v_;
    return *this;
  }
  constexpr self operator++(int) {
    self result = *this;
    ++*this;
    return result;
  }
  constexpr self operator--(int) {
    self result = *this;
    --*this;
    return result;
  }
  constexpr self &operator+=(const self &rhs) {
    v_ += rhs.v_;
    if (v_ >= mod()) v_ -= mod();
    return *this;
  }
  constexpr self &operator-=(const self &rhs) {
    v_ -= rhs.v_;
    if (v_ >= mod()) v_ += mod();
    return *this;
  }
  constexpr self &operator*=(const self &rhs) {
    v_ = (uint32_t)((uint64_t)v_ * rhs.v_ % mod());
    return *this;
  }
  constexpr self &operator/=(const self &rhs) {
    return *this = *this * inverse(rhs);
  }
  constexpr self operator+() const { return *this; }
  constexpr self operator-() const { return self() - *this; }
  constexpr friend self pow(self x, uint64_t y) {
    self res(1);
    for (; y; y >>= 1, x *= x)
      if (y & 1) res *= x;
    return res;
  }
  constexpr friend self inverse(const self &x) {
    auto &&_ = invgcd(x.v_, self::mod());
    if (_.first != 1) throw std::runtime_error("Inverse not exist");
    return _.second;
  }
  constexpr friend self operator+(self lhs, const self &rhs) {
    return lhs += rhs;
  }
  constexpr friend self operator-(self lhs, const self &rhs) {
    return lhs -= rhs;
  }
  constexpr friend self operator*(self lhs, const self &rhs) {
    return lhs *= rhs;
  }
  constexpr friend self operator/(self lhs, const self &rhs) {
    return lhs /= rhs;
  }
  constexpr friend bool operator==(const self &lhs, const self &rhs) {
    return lhs.v_ == rhs.v_;
  }
  constexpr friend bool operator!=(const self &lhs, const self &rhs) {
    return lhs.v_ != rhs.v_;
  }
};
}  // namespace MODINT
using mint = MODINT::Mint<MOD>;
using phimint = MODINT::Mint<MOD - 1>;
namespace primes {
vc<u32> vis;
vc<u32> prime;
vc<phimint> h, mu;
void init_prime(u32 n) {
  h.resize(n);
  mu.resize(n);
  vis.resize(n);
  mu[1] = h[1] = 1;
  for (i64 i = 2; i < n; ++i) {
    if (!vis[i]) {
      vis[i] = i;
      prime.push_back(i);
      h[i] = 1 - i;
      mu[i] = -1;
    }
    for (auto &&j : prime) {
      i64 x = i * j;
      if (x >= n) break;
      vis[x] = j;
      if (i % j) {
        h[x] = h[i] * h[j];
        mu[x] = -mu[i];
      } else {
        h[x] = h[i];
        break;
      }
    }
  }
}
}  // namespace primes
using primes::h, primes::mu;
constexpr mint qpow(mint a, phimint b_) {
  mint res(1);
  for (i64 b = b_.val(); b; b >>= 1, a *= a)
    if (b & 1) res *= a;
  return res;
}
vc<phimint> sumhl;
vc<mint> hh, pdhdkd;
void init_(u32 n) {
  sumhl.resize(n);
  sumhl[1] = h[1];
  for_(i, 2, n - 1) sumhl[i] = sumhl[i - 1] + i * h[i];
  hh.resize(n);
  hh[1] = 1;
  for_(i, 2, n - 1) hh[i] = hh[i - 1] * qpow(i, i);
  vc<mint> dhd(n);
  dhd[1] = 1;
  for_(i, 2, n - 1) dhd[i] = qpow(i, h[i]);
  vc<mint> k(n, 1);
  for_(i, 2, n - 1) {
    mint _ = qpow(i, i * mu[i]);
    for_step_(j, i, n - 1, i) k[j] *= _;
  }
  pdhdkd.resize(n);
  pdhdkd[0] = 1;
  for_(i, 1, n - 1) pdhdkd[i] = pdhdkd[i - 1] * qpow(dhd[i] * k[i], i);
}
constexpr phimint s(i64 n) { return n * (n + 1) / 2; }
mint calc(i64 n, i64 m) {
  if (n > m) swap(n, m);
  mint _ = 1;
  for (i64 l = 1, r; l <= n; l = r + 1) {
    r = min(n / (n / l), m / (m / l));
    _ *= qpow(hh[n / l], s(m / l) * (sumhl[r] - sumhl[l - 1])) *
         qpow(hh[m / l], s(n / l) * (sumhl[r] - sumhl[l - 1])) *
         qpow(pdhdkd[r] / pdhdkd[l - 1], s(n / l) * s(m / l));
  }
  return _;
}
auto solve([[maybe_unused]] int t_ = 0) -> void {
  int t, n;
  cin >> t >> n;
  primes::init_prime(n + OFFSET);
  init_(n + OFFSET);
  while (t--) {
    int l, r;
    cin >> l >> r;
    mint _1 = calc(r, r), _2 = calc(l - 1, l - 1), _3 = calc(r, l - 1);
    cout << _1 * _2 / (_3 * _3) << '\n';
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  solve(i_);
  return 0;
}