[洛谷 3811] 【模板】乘法逆元 {数论}

题目

https://www.luogu.org/problemnew/show/P3811

---

解题思路

本题需要用$O(n)$O(n)的算法
证明与推理如下：
$k=pa+r(r\in [0,p))$k=pa+r(r∈[0,p))
$pa+r\equiv 0(mod\ p)$pa+r≡0(mod p)
$(pa+r)*a^{-1}*r^{-1}\equiv 0(mod\ p)$(pa+r)∗a−1∗r−1≡0(mod p)
$pr^{-1}+a^{-1}\equiv 0(mod\ p)$pr−1+a−1≡0(mod p)
$a^{-1}\equiv -kr^{1}(mod\ p)$a−1≡−kr1(mod p)
$a^{-1}\equiv -k*inv[r](mod\ p)$a−1≡−k∗inv[r](mod p)
$inr[a]\equiv -\left \lfloor \frac{p}{a} \right \rfloor(mod\ p)*inv[r]$inr[a]≡−⌊ap​⌋(mod p)∗inv[r]
$inr[a]\equiv (p-\left \lfloor \frac{p}{a} \right \rfloor)(mod\ p)*inv[r]$inr[a]≡(p−⌊ap​⌋)(mod p)∗inv[r]

---

代码(64)

#include<cstdio>
#include<iostream>
using namespace std; 
long long a,mod,n; 
void write(long long x){if (x>9) write(x/10); putchar(x%10+'0');}
inline long long ksm(long long x,long long y)
{
    long long ans=1; 
    for (;y;(x*=x)%=mod,y>>=1) if (y&1) (ans*=x)%=mod; 
    return ans; 
}
int main()
{
    scanf("%lld%lld",&n,&mod); 
    for (register int i=1;i<=n;i++)
        write(ksm(i,mod-2)),putchar(10); 
}

---

代码(AC)

#include<cstdio>
#include<iostream>
using namespace std; 
long long a,mod,n,f[3000110]; 
void write(long long x){if (x>9) write(x/10); putchar(x%10+'0');}
int main()
{
    scanf("%lld%lld",&n,&mod); f[1]=1; write(1); putchar(10);
    for (register int i=2;i<=n;i++)
	 write((f[i]=(mod-mod/i)*f[mod%i]%mod)),putchar(10); 
}