P7486 「Stoi2031」彩虹

令 S ( a , b ) = ∏ i = 1 a ∏ j = 1 b lcm ⁡ ( a , b ) lcm ⁡ ( a , b ) S(a,b)=\prod\limits_{i=1}^{a}\prod\limits_{j=1}^{b}\operatorname{lcm}(a,b)^{\operatorname{lcm}(a,b)} S(a,b)=i=1∏a​j=1∏b​lcm(a,b)lcm(a,b)。

求：
S ( r , r ) × S ( l − 1 , l − 1 ) S ( r , l − 1 ) × S ( l − 1 , r ) \frac{S(r,r)\times S(l-1,l-1)}{S(r,l-1)\times S(l-1,r)} S(r,l−1)×S(l−1,r)S(r,r)×S(l−1,l−1)​
不妨设 a ≤ b a \leq b a≤b。

令 d p = t dp=t dp=t，则有：
S ( a , b ) = ∏ i = 1 a ∏ j = 1 b lcm ⁡ ( a , b ) lcm ⁡ ( a , b ) = ∏ i = 1 a ∏ j = 1 b i j gcd ⁡ ( a , b ) ( i j gcd ⁡ ( a , b ) ) = ∏ d = 1 a ∏ i = 1 a ∏ j = 1 b i j d ( i j d ) [ gcd ⁡ ( i , j ) = d ] = ∏ d = 1 a ∏ i = 1 ⌊ a d ⌋ ∏ j = 1 ⌊ b d ⌋ ( i j d ) i j d [ gcd ⁡ ( i , j ) = 1 ] = ∏ d = 1 a ∏ i = 1 ⌊ a d ⌋ ∏ j = 1 ⌊ b d ⌋ ( i j d ) i j d ∑ p = 1 ⌊ a d ⌋ μ ( p ) [ p ∣ i ] [ p ∣ j ] = ∏ d = 1 a ∏ p = 1 ⌊ a d ⌋ ∏ i = 1 ⌊ a d ⌋ [ p ∣ i ] ∏ j = 1 ⌊ b d ⌋ [ p ∣ j ] ( i j d ) i j d μ ( p ) = ∏ d = 1 a ∏ p = 1 ⌊ a d ⌋ ∏ i = 1 ⌊ a d p ⌋ ∏ j = 1 ⌊ b d p ⌋ ( i j d p 2 ) i j d p 2 μ ( p ) = ∏ t = 1 a ∏ p ∣ t ∏ i = 1 ⌊ a t ⌋ ∏ j = 1 ⌊ b t ⌋ ( i j t p ) i j t p μ ( p ) \begin{aligned} S(a,b)&=\prod\limits_{i=1}^{a}\prod\limits_{j=1}^{b}\operatorname{lcm}(a,b)^{\operatorname{lcm}(a,b)}\\ &=\prod_{i=1}^{a}\prod_{j=1}^{b}\frac{ij}{\gcd(a,b)}^{(\frac{ij}{\gcd(a,b)})}\\ &=\prod_{d=1}^{a}\prod_{i=1}^{a}\prod_{j=1}^{b}\frac{ij}{d}^{(\frac{ij}{d})[\gcd(i,j)=d]}\\ &=\prod_{d=1}^{a}\prod_{i=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{d}\rfloor}(ijd)^{ijd[\gcd(i,j)=1]}\\ &=\prod_{d=1}^{a}\prod_{i=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{d}\rfloor}(ijd)^{ijd\sum\limits_{p=1}^{\lfloor\frac{a}{d}\rfloor}\mu(p)[p|i][p|j]}\\ &=\prod_{d=1}^{a}\prod_{p=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{i=1}^{\lfloor\frac{a}{d}\rfloor}[p|i]\prod_{j=1}^{\lfloor\frac{b}{d}\rfloor}[p|j](ijd)^{ijd\mu(p)}\\ &=\prod_{d=1}^{a}\prod_{p=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{i=1}^{\lfloor\frac{a}{dp}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{dp}\rfloor}(ijdp^2)^{ijdp^2\mu(p)}\\ &=\prod_{t=1}^{a}\prod_{p|t}\prod_{i=1}^{\lfloor\frac{a}{t}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{t}\rfloor}(ijtp)^{ijtp\mu(p)}\\ \end{aligned} S(a,b)​=i=1∏a​j=1∏b​lcm(a,b)lcm(a,b)=i=1∏a​j=1∏b​gcd(a,b)ij​(gcd(a,b)ij​)=d=1∏a​i=1∏a​j=1∏b​dij​(dij​)[gcd(i,j)=d]=d=1∏a​i=1∏⌊da​⌋​j=1∏⌊db​⌋​(ijd)ijd[gcd(i,j)=1]=d=1∏a​i=1∏⌊da​⌋​j=1∏⌊db​⌋​(ijd)ijdp=1∑⌊da​⌋​μ(p)[p∣i][p∣j]=d=1∏a​p=1∏⌊da​⌋​i=1∏⌊da​⌋​[p∣i]j=1∏⌊db​⌋​[p∣j](ijd)ijdμ(p)=d=1∏a​p=1∏⌊da​⌋​i=1∏⌊dpa​⌋​j=1∏⌊dpb​⌋​(ijdp2)ijdp2μ(p)=t=1∏a​p∣t∏​i=1∏⌊ta​⌋​j=1∏⌊tb​⌋​(ijtp)ijtpμ(p)​
令 s ( x ) = ∑ i = 1 x i = x ( x + 1 ) 2 s(x)=\sum\limits_{i=1}^{x}i=\frac{x(x+1)}{2} s(x)=i=1∑x​i=2x(x+1)​， f ( x ) = ∏ i = 1 x i i f(x)=\prod\limits_{i=1}^{x}i^i f(x)=i=1∏x​ii，则有：
∏ i = 1 n ∏ j = 1 m ( i j ) i j = f ( n ) s ( m ) × f ( m ) s ( n ) \prod_{i=1}^{n}\prod_{j=1}^{m}(ij)^{ij}=f(n)^{s(m)}\times f(m)^{s(n)} i=1∏n​j=1∏m​(ij)ij=f(n)s(m)×f(m)s(n)
令其为 G ( n , m ) G(n,m) G(n,m)。

另有：
∏ i = 1 n ∏ j = 1 m ( t p ) i j = ( t p ) s ( n ) × S ( m ) \prod_{i=1}^{n}\prod_{j=1}^{m}(tp)^{ij}=(tp)^{s(n)\times S(m)} i=1∏n​j=1∏m​(tp)ij=(tp)s(n)×S(m)
带回原式有：
∏ t = 1 a ( ∏ p ∣ t ( G ( ⌊ a t ⌋ , ⌊ b t ⌋ ) × ( t p ) s ( ⌊ a t ⌋ ) × s ( ⌊ b t ⌋ ) ) p μ ( p ) ) t \prod_{t=1}^{a}\left( \prod_{p|t}\left( G(\lfloor\frac{a}{t}\rfloor,\lfloor\frac{b}{t}\rfloor) \times (tp)^{s(\lfloor\frac{a}{t}\rfloor)\times s(\lfloor\frac{b}{t}\rfloor)} \right)^{p\mu(p)} \right)^{t} t=1∏a​⎝⎛​p∣t∏​(G(⌊ta​⌋,⌊tb​⌋)×(tp)s(⌊ta​⌋)×s(⌊tb​⌋))pμ(p)⎠⎞​t

另 h ( x ) = ∑ d ∣ x d μ ( d ) , y ( x ) = ∏ d ∣ x d d μ ( d ) h(x)=\sum\limits_{d|x}d\mu(d),y(x)=\prod\limits_{d|x}d^{d\mu(d)} h(x)=d∣x∑​dμ(d),y(x)=d∣x∏​ddμ(d)，则有：
∏ t = 1 a G ( ⌊ a t ⌋ , ⌊ b t ⌋ ) t ⋅ h ( t ) × ( t h ( t ) × y ( t ) ) t × s ( ⌊ a t ⌋ ) × s ( ⌊ b t ⌋ ) \prod_{t=1}^{a}G(\lfloor\frac{a}{t}\rfloor,\lfloor\frac{b}{t}\rfloor)^{t \cdot h(t)}\times (t^{h(t)}\times y(t))^{t\times s(\lfloor\frac{a}{t}\rfloor)\times s(\lfloor\frac{b}{t}\rfloor)} t=1∏a​G(⌊ta​⌋,⌊tb​⌋)t⋅h(t)×(th(t)×y(t))t×s(⌊ta​⌋)×s(⌊tb​⌋)
再令 h h ( x ) = x × h ( x ) , y y ( x ) = ( x h ( x ) × y ( x ) ) x hh(x)=x\times h(x),yy(x)=(x^{h(x)}\times y(x))^{x} hh(x)=x×h(x),yy(x)=(xh(x)×y(x))x，可得：
∏ t = 1 a G ( ⌊ a t ⌋ , ⌊ b t ⌋ ) h h ( t ) × y y ( t ) s ( ⌊ a t ⌋ ) × s ( ⌊ b t ⌋ ) \prod_{t=1}^{a}G(\lfloor\frac{a}{t}\rfloor,\lfloor\frac{b}{t}\rfloor)^{hh(t)}\times yy(t)^{s(\lfloor\frac{a}{t}\rfloor)\times s(\lfloor\frac{b}{t}\rfloor)} t=1∏a​G(⌊ta​⌋,⌊tb​⌋)hh(t)×yy(t)s(⌊ta​⌋)×s(⌊tb​⌋)
最后前缀和 + \text{+} + 前缀积 + \text{+} + 数论分块即可。

再加一个小优化，设一个阈值 S S S，对于 1 ≤ t < S 1 \leq t < S 1≤t<S 的直接暴力算，因为这部分 l , r l,r l,r 相差较小。

对于 S ≤ t ≤ n S \leq t \leq n S≤t≤n 的，再数论分块算。

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

inline void write(int x)
{
	if(x < 0)
	{
		putchar('-');
		x = -x;
	}
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

const int _ = 1e6 + 7, mod = 32465177;

bool vis[_];

int cnt, pr[_], mu[_], f[_], h[_], y[_];

int ksm(int x, int y)
{
	int res = 1;
	while(y)
	{
		if(y & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return res;
}

void init()
{
	mu[1] = 1;
	f[1] = 1;
	y[1] = 1;
	for(int i = 2; i <= _ - 7; ++i)
	{
		f[i] = 1ll * f[i - 1] * ksm(i, i) % mod;
		y[i] = 1;
		if(!vis[i])
		{
			pr[++cnt] = i;
			mu[i] = -1;
		}
		for(int j = 1; j <= cnt && i * pr[j] <= _ - 7; ++j)
		{
			int p = i * pr[j];
			vis[p] = 1;
			if(i % pr[j] == 0)
			{
				mu[p] = 0;
				break;
			}
			mu[p] = -mu[i];
		}
	}
	for(int i = 1; i <= _ - 7; ++i)
		for(int j = 1; i * j <= _ - 7; ++j)
		{
			h[i * j] = ((h[i * j] + mu[i] * i) % (mod - 1) + (mod - 1)) % (mod - 1);
			y[i * j] = 1ll * y[i * j] * ksm(i, i * mu[i] + mod - 1) % mod;
		}
	for(int i = 1; i <= _ - 7; ++i)
	{
		y[i] = ksm(1ll * ksm(i, h[i]) * y[i] % mod, i);
		h[i] = 1ll * h[i] * i % (mod - 1);
	}
	y[0] = 1;
	for(int i = 2; i <= _ - 7; ++i)
	{
		y[i] = 1ll * y[i - 1] * y[i] % mod;
		h[i] = (h[i] + h[i - 1]) % (mod - 1);
	}
}

int s(int x)
{
	return 1ll * x * (x + 1) / 2 % (mod - 1);
}

int g(int x, int y)
{
	return 1ll * ksm(f[x], s(y)) * ksm(f[y], s(x)) % mod;
}

int hh(int l, int r)
{
	return ((h[r] - h[l - 1]) % (mod - 1) + (mod - 1)) % (mod - 1);
}

int yy(int l, int r)
{
	return 1ll * y[r] * ksm(y[l - 1], mod - 2) % mod;
}

int S(int a, int b)
{
	if(a > b) swap(a, b);
	int res = 1;
	for(int i = 1, j; i <= a; i = j + 1)
	{
		j = min(a / (a / i), b / (b / i));
		res = 1ll * res * ksm(g(a / i, b / i), hh(i, j)) % mod * ksm(yy(i, j), 1ll * s(a / i) * s(b / i) % (mod - 1)) % mod; 
	}
	return res;
}

int solve(int l, int r)
{
	swap(l, r);
	int ans1 = 1ll * S(r, r) * S(l - 1, l - 1) % mod, ans2 = 1ll * S(r, l - 1) * S(l - 1, r) % mod;
	return 1ll * ans1 * ksm(ans2, mod - 2) % mod;
}

signed main()
{
	init();
	int t = read(), n = read();
	while(t--)
	{
		write(solve(read(), read()));
		putchar('\n');
	}
}