#P7486. 「Stoi2031」彩虹

「Stoi2031」彩虹

题目背景

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

题目描述

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

输入格式

第一行两个正整数 t,nt,n

接下来 tt 行,每行两个正整数 li,ril_i,r_i,表示一次询问。

输出格式

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

3 7
1 3
2 3
7 7

21072733
12145631
823543

提示

简述版题意:

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

样例解释:

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

对于第 22 次询问,ans=22×33×(66)2ans=2^2 \times 3^3 \times (6^6)^2ansmod32465177=12145631ans \bmod{32465177}=12145631

对于第 33 次询问,ans=77=823543ans=7^7=823543

数据范围:

对于 30%30\% 的数据,1n103,t=11 \le n \le 10^3,t=1

对于 60%60\% 的数据,1n105,t=11 \le n \le 10^5,t=1

对于 100%100\% 的数据,$1 \le n \le 10^6,1 \le t \le 10,1 \le l_i \le r_i \le n$。