题目背景

这是一道模板题

题目描述

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

输入输出格式

输入格式：

一行n,p

输出格式：

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

输入输出样例

输入样例#1：

10 13

输出样例#1：

179108112534

说明

1≤n≤3×10​6​​,n<p<20000528

输入保证 pp 为质数。

费马小定理：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define ll long long 6 using namespace std; 7 int n,p; 8 int fast(ll a,ll b){ 9     ll ans=1;10     while(b){11         if(b&1)ans=(ans*a)%p;12         a=(a*a)%p;13         b>>=1;14     }15     return ans;16 }17 int main(){18     scanf("%d%d",&n,&p);19     for(int i=1;i<=n;i++)20         printf("%d\n",fast(i,p-2));21     return 0;22 }
        
       
      
     

扩展欧几里得：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 void ex_gcd(int a,int b,int &x,int &y){ 7     if(b==0){x=1,y=0;return;} 8     ex_gcd(b,a%b,x,y); 9     int tmp=x;x=y;y=tmp-(a/b)*y;10 }11 int main(){12     int a,b,x,y;13     scanf("%d%d",&a,&b);14     for(int i=1;i<=a;i++){15         ex_gcd(i,b,x,y);16         printf("%d\n",(x+b)%b);17     }18     return 0;19 }
        
       
      
     

线性计算：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 int ans[3000010],n,p; 7 int main(){ 8     scanf("%d%d",&n,&p); 9     ans[1]=1;puts("1");10     for(int i=2;i<=n;i++){11         ans[i]=(long long)(p-p/i)*ans[p%i]%p;12         printf("%d\n",ans[i]);13     }14     return 0;15 }