题解 P3811 【【模板】乘法逆元】

一个刚学数论的萌新，总结了一下这题的大部分做法

//一、费马小定理+快速幂  O(nlogn) 64分

#include<cstdio>

using namespace std;

typedef long long ll;

int a,b;

inline ll pow(ll x,ll p) {

    ll ans=1;

    x%=b;

    while(p) {

        if (p&1) ans=ans*x%b;

        x=x*x%b;

        p>>=1;

    }

    return ans%b;

}

inline void write(int x) {

    if(x>9) write(x/10);

    putchar(x%10^48);

}

int main() {

    scanf("%d%d",&a,&b);

    for (int i=1; i<=a; i++) {

        write(pow(i,b-2));

        putchar('\n');

    }

}

//二、exgcd O(nlogn)  80分

#include<cstdio>

using namespace std;

typedef int ll;

ll x,y,a,b;

inline void exgcd(ll a,ll b) {

    if (!b) x=1,y=0;

    else {exgcd(b,a%b); int t=x; x=y,y=t-a/b*y;}

}

inline void write(int x){

    if(x>9) write(x/10);

    putchar(x%10^48);

}

int main() {

    scanf("%d%d",&a,&b);

    for (int i=1; i<=a; i++) {

        exgcd(i,b);

        write((x%b+b)%b);

        putchar('\n');

    }

}

//三、费马小定理+快速幂+线性筛 合数O(1)，质数O(nlogn) 80分

#include <cstdio>

using namespace std;

typedef long long ll;

ll n,p,inv[3000010],vis[3000010];

ll pow(ll x,int b) {

    ll ans=1;

    for (int i=b; i; i>>=1,x=x*x%p)

        if (i&1) ans=ans*x%p;

    return ans%p;

}

void work() {

    inv[1]=vis[1]=1;

    for (int i=2; i<=n; i++)

        if (!vis[i]) {

            vis[i]=1;

            inv[i]=pow(i,p-2);

            for (int j=2; j<=i && j*i<=n; j++)

                vis[i*j]=1,inv[i*j]=(inv[i]*inv[j])%p;

        }

}

int main() {

    scanf("%lld%lld",&n,&p);

    work();

    for (int i=1; i<=n; i++) printf("%lld\n",inv[i]);

    return 0;

}

//四、阶乘+1次快速幂 O(n) 100分 607ms

#include<cstdio>

#define ll long long

using namespace std;

int n,p;

ll c[3000005],ans[3000005];

ll ksm(ll x,ll y)

{

    ll an=1;

    while(y)

    {

        if(y&1)

            an=(an*x)%p;

        x=(x*x)%p;

        y>>=1;

    }

    return an;

}

int main()

{

    scanf("%d%d",&n,&p);

    c[0]=1;

    for (int i=1;i<=n;i++) c[i]=(c[i-1]*i)%p;

    ll pow=ksm(c[n],p-2),k;

    for(int i=n;i;i--)

    {

        k=(pow*i)%p;

        ans[i]=(pow*c[i-1])%p;

        pow=k;

    }

    for(int i=1;i<=n;i++)

        printf("%lld\n",ans[i]);

}

//五、线性递推 O(n) 100分 560ms

#include<cstdio>

#define ll long long

using namespace std;

ll inv[3000005]={0,1};

int main()

{

    int n,p;

    scanf("%d%d",&n,&p);

    printf("1\n");

    for (int i=2;i<=n;i++)

    printf("%d\n",inv[i]=(ll)p-(p/i)*inv[p%i]%p);

    return 0;

}

巴特西

题解 P3811 【【模板】乘法逆元】

最新文章

热门文章