#P5282. 【模板】快速阶乘算法

    ID: 111 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>倍增快速傅里叶变换,FFT快速数论变换 NTT数论数学

【模板】快速阶乘算法

题目背景

有一天,NaCly_Fish 无意间看到一种高效求阶乘模大质数的算法,但是她太菜,并不会写。
于是她就暴力造了数据,请您帮忙写出 std 吧。

什么,您问为什么不保证模数可以 NTT?
那样的话就可能被打表水过,或者答案就爆 int 了。

反正您是神仙,肯定能秒掉这题。

题目描述

给你正整数 nn,和一个质数 pp,你需要求出:

n! mod pn! \text{ mod } p

TT 组数据。

输入格式

第一行一个正整数 TT,表示数据组数。
接下来 TT 行,每行两个正整数 n,pn,p,意义如题目描述。

输出格式

输出 TT 行,表示每组数据的答案。

4
16777216 998244353
72267859 998244353
2333333 19260817
1919810 2147481811
789885751
569626621
16351109
1416439247

提示

数据范围:

对于 10%10\% 的数据:p=998244353p = 998244353
对于另外 10%10\% 的数据:p=1004535809p = 1004535809
对于 100%100\% 的数据:1n<p23111\le n < p \le 2^{31}-11T51 \le T \le 5
保证 pp 为质数。

【提示】
请确保你的算法时间复杂度不高于 Θ(nlogn)\Theta(\sqrt n \log n),时限为 std 的十倍以上。