#1511. 「MtOI2019」幽灵乐团

「MtOI2019」幽灵乐团

题目描述

白玉楼中,冥界的音乐会开始了。

Lusana ,Lyrica 和 Merlin 正在演奏。


东风谷 早苗 (Kochiya Sanae) 非常喜欢幽灵乐团的演奏,她想对她们的演奏评分。

因为幽灵乐团有 33 个人,所以我们可以用 33 个正整数 A,B,CA,B,C 来表示出乐团演奏的分数,她们的演奏分数可以表示为

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\mathrm{lcm}(i,j)}{\gcd(i,k)}\right)^{f(\text{type})} $$

因为音乐在不同的部分会有不同的听觉感受,所以 type\text{type} 会在 {0,1,2}\{0,1,2\} 中发生变化,其中:

$$\begin{split} &f(0)=1 \\ &f(1)=i \times j \times k \\ &f(2)=\gcd (i,j,k) \end{split} $$

因为乐团的歌实在太好听了,导致分数特别高,所以她们的分数要对给定的正整数 pp 取模。

因为有很多歌曲要演奏,所以早苗给出了 TT 组询问。

输入格式

第一行两个正整数 TTpp,含义详见题目描述。

接下来 TT 行,每行三个正整数 A,B,CA,B,C 表示每组询问。

输出格式

TT 行,每行三个正整数分别表示 type={0,1,2}\text{type}= \{0,1,2\} 的时候给定式子的值

样例

3 998244853
1 1 1
2 2 2
3 3 3
1 1 1
16 4096 16
180292630 873575259 180292630

数据范围与提示

子任务

对于 10%10\% 的数据:1A,B,C501\leq A,B,C\leq 50

对于 20%20\% 的数据:1A,B,C1001\leq A,B,C\leq 100

另有 10%10\% 的数据:1A,B,C100,A=B=C1\leq A,B,C\leq 100,A=B=C

对于 60%60\% 的数据:1A,B,C1031\leq A,B,C\leq 10^3

对于 100%100\% 的数据:$1\leq A,B,C\leq 10^5,10^7 \leq p \leq 1.05\times 10^9,T =70$,保证 pp 是一个质数。


早苗非常善良,就算你不知道所有的正确答案,她也会给你一些分数。

  • 如果你的第一列是正确的,她将会给你这个测试点 20%20\% 的分数。

  • 如果你的第二列是正确的,她将会给你这个测试点 40%40\% 的分数。

  • 如果你的第三列是正确的,她将会给你这个测试点 40%40\% 的分数。

所以就算你不知道答案是什么,也请你在你不知道的那些地方输出 [0,231)[0,2^{31}) 内的整数,否则可能会造成不可预估的错误。

题目来源

迷途之家 2019 联赛 (MtOI2019) T5

出题人: CYJian