点击刷新
\(\texttt{例题}\)
给定 \(n,p\)， 求 \(1\sim n\) 中所有整数在模 \(p\) 意义下的乘法逆元。
保证 \(p\) 为质数且 \(p>n\)。
\(\texttt{乘法逆元}\)
A：什么是在模 \(p\) 意义下的乘法逆元？
Q：\(a\) 在模 \(p\) 意义下的乘法逆元是满足 \(ax\equiv1(mod\quad p)\) 的 \(x\) 的值。\(x\) 又可以写成 \(a^{-1}\)。
\(\texttt{方法一：递推}\)
适用于求大范围内所有数的逆元
设 \(k,r\) 满足 \(p/i=k......r\)。
则有 \(k=\lfloor \dfrac{p}{i}\rfloor,\quad r=p\%i\)
那么原方程变为：
\[ki+r\equiv 0(mod\quad p)
\]
等式两边同乘 \(i^{-1}\)
\[k\times i\times i^{-1}+r\times i^{-1}\equiv 0(mod\quad p)
\]
\[k+r\times i^{-1}\equiv 0(mod\quad p)
\]
\[r\times i^{-1}\equiv -k(mod\quad p)
\]
等式两边同乘 \(r^{-1}\)
\[r\times i^{-1}\times r^{-1}\equiv -k\times r^{-1}(mod\quad p)
\]
\[i^{-1}\equiv -(p/i)(p\%i)^{-1}(mod\quad p)
\]
\[i^{-1}\equiv (p-p/i)(p\%i)^{-1}(mod\quad p)
\]
因为 \(p\%i<i\)，所以 \(p\%i\) 的逆元一定是之前处理过的。
因此，我们就得到了递推式。设 \(f(i)=i^{-1}\)，则有：
\[f(i) = [(p-p/i)\times f(p\%i)]\%p
\]
\(\texttt{代码}\)
#include <bits/stdc++.h>
using namespace std;
long long a[20000528],n,p;
int main()
{
cin>>n>>p;
a[1]=1;//无论p是多少，1的逆元一定是1
cout<<1<<endl;
for(register long long i=2; i<=n; i++)
{
a[i]=(p-p/i)*a[p%i]%p；//递推式
printf("%lld\n",a[i]);
}
return 0;
}
\(\texttt{方法二：扩展欧几里得}\)
适用于单个乘法逆元求解
对于 \(ax\equiv 1(mod\quad p)\) 这个式同余方程，进行化简后得：
\[ax+py=1
\]
因为 \(p\) 为质数且 \(p>n\)，所以 \(gcd(a,p)=1\)，于是原式又可以写成：
\[ax+py=gcd(a,p)
\]
然后便可以用扩展欧几里得求解。
戳这里
© 著作权归作者所有
举报
相关热门文章
发表评论
0/200
