P3811

· · 个人记录

【模板】乘法逆元

数学知识还是写在活页纸上比较方便学习。

这里就要用线性递推式。。。

i^{-1}\equiv -\lfloor\dfrac{p}{i}\rfloor\times(p\mod i)^{-1}\pmod{p}

时间复杂度 O(n) 。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=3e6;

ll n,p;

ll inv[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();p=read();inv[1]=1;

    write(inv[1]);putchar('\n');

    for(ll i=2;i<=n;i++) {
        inv[i]=(p-p/i)*inv[p%i]%p;
        write(inv[i]);putchar('\n');
    }

    return 0;
}