P3811 【模板】乘法逆元

题目背景

这是一道模板题

题目描述

给定n,p求1~n中所有整数在模p意义下的乘法逆元。

输入输出格式

输入格式：

一行n,p

输出格式：

n行,第i行表示i在模p意义下的逆元。

输入输出样例

输入样例#1：复制

10 13

输出样例#1：复制

说明

1 \leq n \leq 3 \times 10 ^ 6, n < p < 200005281≤n≤3×106,n<p<20000528

输入保证 pp 为质数。

思路：求逆元，用inv(a)表示一个数的逆元。

特别注意：本题卡输出cout

方法一：费马小定理。

　　我们已知费马小定理为：a^^(p-1)≡1(mod p)

两边同时除以a得到：a^^(p-2)≡1/a(mod p)也就是a^^(p-2)≡inv(a) (mod p)

所以：inv(a)≡a^^(p-2) (mod p)

然后就可以用快速幂求解。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,p;

long long pow(long long a,long long x,long long p){

    long long s=%p;

    for(;x;x>>=){

        if(x&)    s=s*a%p;

        a=a*a%p;

    }

    return s;

}

int main(){

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

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

        cout<<pow(i,p-,p)<<endl;

}

费马小定理时间复杂度n(log n) TLE

方法二：拓展欧几里得。

　　如果a*x+b*y=1在gcd(a,b)=1的情况下有解，那么这个解中的x就是a关于b的逆元，y就是b关于a的逆元。

　　证明：a*x%b+b%y%b=1%b;

　　　　 a*x%b=1%b;

　　　　 a*x≡1(mod b);

所以x是a关于b的逆元，同理，可证明y是b关于a的逆元。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,p;

void ex_gcd(long long a,long long b,long long &x,long long &y,long long &d){

    if(!b){ x=;y=;d=a; }

    else{

        ex_gcd(b,a%b,y,x,d);

        y-=x*(a/b);

    }

}

int inv(long long t,long long p){

    long long d,x,y;

    ex_gcd(t,p,x,y,d);

    return d==?(x%p+p)%p:-;

}

int main(){

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

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

        printf("%d\n",inv(i,p));

}

拓展欧几里得 83

方法三：因为p是一个质数，所以一定有inv(a)=(p-p/a)*inv(p%a)%p;

　　证明：设x=p%a,y=p/a;

　　于是有：(x+y*a)%p=0;

　　移项得：x%p=(-y)*a%p;

　　x*inv(a)%p=(-y)%p;

　　inv(a)=(p-y)*inv(x)%p;

　　所以：inv(a)=(p-p/a)*inv(p%a)%p;

　然后一直递归到1为止。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 3000010

using namespace std;

int n,p;

int inv[MAXN];

int main(){

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

    inv[]=;

    printf("1\n");

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

        inv[i]=(p-p/i)*1ll*inv[p%i]%p;

        printf("%d\n",inv[i]);

    }

}

。。。

巴特西

洛谷 P3811 【模板】乘法逆元

P3811 【模板】乘法逆元

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章