先无良宣传一下博客wwwwww
文章列表 - 核融合炉心 - 洛谷博客

• 乘法逆元:

  对于一个模数 \(p\) 和一个除数 \(x\) ,往往可以找到一个特殊数 \(y\) ,
  将\(\div x\) 改为 \(\times y\) , 即可代替。

  这个数 \(y\) ,称为 \(x\) 的"逆元",记作 \(inv(x)\) 。

  例:
  \(3 \div 3 \times 4 (\mod 11)\)
  \(=3 \times 4 \times 4 (\mod 11)\)
  \(= 4\)
  其中, \(4\) 即为模数为 \(11\) 时 , \(3\) 的 逆元.

  通过定义与例子 , 不难看出逆元与原数之间的关系:
  \(\large x \times inv(x) \equiv 1(\mod p)\)

---

• 求解模的逆元:

P3811 【模板】乘法逆元

有 \(4\) 种方法可以求得 模的逆元

1. 根据 扩展欧几里得 :

   模数可以 不为质数

   \(x \times inv(x) \equiv 1(\mod p)\) 其中 \(x,p\) 都是已知的。

   有没有很眼熟 ？

   这就是一个
   未知数为 \(inv(x)\) , 方程右侧的 \(c=1\) 的同余方程 ,

   求 \(inv(x)\) 的值 , 解出此同余方程即可。

   关于 扩展欧几里得 与 解同余方程 ，
   详见： 欧几里得 与 扩展欧几里得 - 核融合炉心 - 洛谷博客

---

1. 根据 费马小定理 :

   #### 只适用于模数为质数的情况

   由费马小定理：
   \(\large x ^{p-1} \equiv 1 \pmod p\)

   故有 : $ x ^{p-1}\equiv x \times inv(x) \pmod p$

   等式两侧同除x , 有: \(inv(x) \equiv x ^{p-2} \pmod p\)

   之后可以通过快速幂求余 , 求得 \((x ^{p-2} ) \% p\) 的值 ,
   即可直接得到 \(inv(x)\) 的值

---

1. 递推法 :

   只适用于模数为质数的情况

   如果要解模的逆元的数 , 数量很多，但是连续 , 那该怎么办 ?

   就可以使用递推法 。

   \(i\) 模 \(p\) 意义下的逆元 \(inv(i)\) 可表示为 :　

   \(\large inv(i) = -\lfloor \frac{p}{i}\rfloor \times inv(p\% i)\% p\)

   • 证明:

     设 $p=k\times i + r $ , \((k,r \in Z)\)

     因为 : \(p \equiv 0 (\mod p)\) ,

     则 : \((k\times i + r) \equiv 0 (\mod p)\)

     使方程两边同乘 : \(inv(i)\times inv(r)\) ,

     根据 逆元的性质 ，则:

     \((inv(i) \times i )\% p=1\) ， \((inv(r) \times r )\% p=1\) ;

     原式变为 ：

     \(k \times 1 \times inv(r) + 1\times inv(i) \equiv 0 (\mod p)\)

     \(inv(i) \equiv -k\times inv(r)\)

     又因为 : $p=k\times i + r $

     原式变为 ： \(inv(i) \equiv -\lfloor \frac{p}{i}\rfloor\times inv(p\%i) (\mod p)\)

     即 ： \(inv(i) = -\lfloor \frac{p}{i}\rfloor \times inv(p\% i) \% p\)

     又因为 : \((p\% i) <i\) ,

     则 : \(inv(p\% i)\) 在求出 \(inv(i)\) 前便已求 , 可以进行递推

     原式得证 。

     显然 , 求得的 \(inv(i)\) 不一定为最小整数解

     若要获得最小正整数解,需要再加这样一步操作:

     使 \(-\lfloor \frac{p}{i}\rfloor\) 先加上一个 \(p\) , 再将其模掉 。

     即 : \(inv(i) = (p - \lfloor \frac{p}{i}\rfloor)\times inv(p \% i) \% p;\)

---

1. 阶乘逆元法：

   #### 只适用于模数为质数的情况

   设 \(f(i)=inv(i!)\) , $  g(i)=i! $

   则： \(f(i-1) = f(i)\times i\)

   • 证明:

     \(f(i-1)=\frac{1}{\ (i-1)\ !}=\frac{1}{i\ !}\times i =f(i)\times i\)

   假设要求 \([1,n]\) 中所有数的逆元

   先求得 \([1,n]\) 中所有数的阶乘

   再用 费马小定理 求得 \(f(n)\) 的值

   之后递推出 \(f(1 \sim n)\) 的值

   但是 \(inv(1! \sim n! )\) 并不是我们想要的答案

   需要继续转化。

   可知 : $inv(i) = inv(i!) \times(i-1) ! $

   • 证明 :

     \(inv(i)=\frac{1}{i}=\frac{1}{i\ !}\times (i-1)\ ! = inv(i!)\times (i-1)!\)

   按照上述方法转换,
   可得:

   \(inv(i)=f(i)\times (i-1)!\)

   即得答案 。

---

• 回到此题

先看一眼数据范围:
\(1\leqslant n \leqslant 3\times 10^6\) , \(n<p<20000528\)
输入保证 \(p\) 为质数.

很明显, 扩欧法 和 快速幂法 都被卡了 .

由于区间连续 , 且模数 \(p\) 为质 ,
则可以进行 线性递推

原理上面讲的非常清楚.

代码如下:

递推法 :

#include<cstdio>
using namespace std;
long long n,p;
long long ans[5000010]={0,1};
int main()
{
   scanf("%lld%lld",&n,&p);
   printf("1\n");
   for(long long i=2;i<=n;i++) //线性递推
     {
       ans[i]=(long long)(p-p/i)*ans[p%i]%p;
       printf("%lld\n",ans[i]); 
     }
}

阶乘逆元法：

#include<cstdio>
#define ll long long
using namespace std;
ll mul(ll a,ll b,ll mod) //快速幂模板
{
  ll ans=1;
  while(b)
    {
      if(b&1) ans=ans*a%mod;
      a=(a*a)%mod;
      b>>=1;
    }
  return ans%mod;
}
ll n,p;
ll c[5000010]={1};
ll f[5000010];
int main()
{
  scanf("%lld%lld",&n,&p);
  for(int i=1;i<=n;i++)
    c[i]=(c[i-1]*i)%p;
    
  f[n]=mul(c[n],p-2,p); //获得inv(n!)
  
  for(int i=n-1;i>=1;i--) //递推阶乘的逆元
    f[i]=(f[i+1]*(i+1))%p;
    
  for(int j=1;j<=n;j++) //转化并输出
    printf("%lld\n",(f[j]*c[j-1])%p);
}

---