[模板]乘法逆元

本博客所有代码基于题目 luogu_P3811

逆元：

定义：

Second：欧拉定理

 1 #include<cstdio> 
 2 #define ll long long
 3 using namespace std;
 4 int n,p;
 5 inline ll ksm(ll a,ll b){
 6     ll ans=1;
 7     a%=p;
 8     while(b){
 9         if(b&1) ans=ans*a%p;
10         a=a*a%p;
11         b>>=1;
12     }
13     return ans%p;
14 }
15 void write(ll x){
16     if(x<0) putchar('-'),x=-x;
17     if(x>9) write(x/10);putchar(x%10^48);
18 }
19 int main(){
20     scanf("%d%d",&n,&p);
21     for(int i=1;i<=n;i++)
22         write(ksm(i,p-2)),putchar('
');
23     return 0;
24 }

TLE_83分

Third:解不定方程

 1 #include<cstdio>
 2 using namespace std;
 3 int x,y;
 4 void exgcd(int a,int b){
 5     if(!b){x=1,y=0;return ;}
 6     exgcd(b,a%b);
 7     int t=x;
 8     x=y,y=t-a/b*y;
 9 }
10 void write(int x){
11     if(x>9) write(x/10);
12     putchar(x%10^48);
13 }
14 int main(){
15     int n,p;
16     scanf("%d%d",&n,&p);
17     for(int i=1;i<=n;++i)
18         exgcd(i,p),write((x%p+p)%p),putchar('
');
19     return 0;
20 }

AC_1240ms

Forth：线性递推

　　复杂度 O(n)
　　

 1 #include<cstdio>
 2 #define ll long long
 3 using namespace std;
 4 const int maxn=3e6+5;
 5 ll inv[maxn]={0,1};
 6 int main(){
 7     int n,p;
 8     scanf("%d%d",&n,&p);
 9     printf("1
");
10     for(int i=2;i<=n;i++)
11         inv[i]=(ll)p-(p/i)*inv[p%i]%p,printf("%d
",inv[i]);
12     return 0;
13 }

AC_664ms

[模板]乘法逆元

本博客所有代码基于题目 luogu_P3811

逆元：

定义：

求法：

First：费马小定理

Second：欧拉定理

Third:解不定方程

Forth：线性递推