SP16211 Wilson定理题解

Cuiyi_SAI · 2022-06-14 21:36:46 · 题解

引入

求 n!\bmod p，n,p\le2\cdot 10^9

如果直接暴力求 n! 并取模，肯定会因为数据范围而 \color{DarkBlue}TLE，那我们要如何考虑优化求阶乘的过程呢？

Wilson 定理

当 p 为质数

为什么呢？显然，在 [1,p-1] 中所有数，在模 p 意义下的乘法逆元都在 [1,p-1] 的范围内。因此，若这个数的乘法逆元不是它自己本身，那么在模意义下的求阶乘过程中，一个数与它的逆元相乘就同余为 1，在模 p 意义下相当于直接抵消。

因此，逆元不是自己本身的数，在模意义下不对 (p-1)! 产生贡献，即 (p-1)! 在模 p 下的值只取决于哪些逆元是自己本身的数，就是只有 1 和 p-1 了，因此 (p-1)!\equiv 1^{-1}\cdot (p-1)^{-1}\equiv p-1\pmod p

解题思路

对于 n>p 的情况，由于 n! 中含有 p，因此肯定能被 p 整除，故此时 n!\equiv 0\pmod p

考虑到 |p-n| 肯定不大，因此如果我们得到了 (p-1)! ，那我们就可以直接利用 (p-1)! 来暴力求出 n! ，即 n!=\dfrac{(p-1)!}{\prod\limits_{i=n+1}^{p-1}i}，此时只需处理出分母逆元就行了。

而求 (p-1)! 我们上面也提到了，就是直接考虑利用 Wilson 定理，这样可以快速求出 (p-1)! 在模 p 意义下的值，即为 p-1。

回头来看，我们利用了 Wilson 定理可以快速求 (p-1)! 的性质，将 n! 分块处理，优化了复杂度。

CODE

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,n,p,x,y;
int exgcd(int l,int r)
{
    if(r==0)
    {
        x=1;
        y=0;
        return l;
    }
    int d=exgcd(r,l%r);
    int s=x;
    x=y;
    y=s-l/r*y;
    return d;
}
int mod_slover(int a,int n,int b)
{
    int g=exgcd(a,b);
    if(n%g!=0) return 0;
    x=(x*(n/g))%p;
    x=(x%(b/g)+(b/g))%(b/g);
    return x;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t)
    {
        t--;
        cin>>n>>p;
        if(n>=p)
        {
            cout<<0<<'\n';
            continue;
        }
        int num=1;
        for(int i=n+1;i<p;i++) num=num*i%p;
        cout<<(p-1)*mod_slover(num,1,p)%p<<'\n';  //直接利用 Wilson 和乘法逆元求得 n!
    }
    return 0;
}