P3811乘法逆元
题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入输出格式
输入格式：
一行n,p
输出格式：
n行,第i行表示i在模p意义下的逆元。
扩欧求解同余方程
#include<bits/stdc++.h> using namespace std; #define ll long long ll int n,p,x,y; void gcd(ll a,ll b,ll &x,ll &y) { if(!b){x=1;y=0;} else gcd(b,a%b,y,x),y-=(a/b)*x; } int main() { cin>>n>>p; for(int i=1;i<=n;i++) { gcd(i,p,x,y); cout<<(x%p+p)%p<<endl; } }
费马小定理
#include<bits/stdc++.h> using namespace std; #define ll long long ll int n,p,x,y; long long int power(int b,int k) { if(!k)return 1; else{ long long a=power(b,k/2); if(!(k%2))return (a*a)%p; else return (a*a*b)%p; } } int main() { cin>>n>>p; for(int i=1;i<=n;i++) { ll ans=power(i,p-2); cout<<(ans%p+p)%p<<endl; } }
递推
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=3e6+5; ll inv[maxn]={0,1}; int main(){ int n,p; scanf("%d%d",&n,&p); printf("1 "); for(int i=2;i<=n;i++) inv[i]=(ll)p-(p/i)*inv[p%i]%p,printf("%d ",inv[i]); }