乘法逆元

ref:http://blog.csdn.net/acdreamers/article/details/8220787

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define MN 20001005
 5 using namespace std;
 6 inline int in(){
 7     int x=0;bool f=0; char c;
 8     for (;(c=getchar())<'0'||c>'9';f=c=='-');
 9     for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
10     return f?-x:x;
11 }
12 int inv[MN],n,p;
13 int main()
14 {
15     n=in();p=in();
16     inv[1]=1;printf("%d
",inv[1]);
17     for (int i=2;i<=n;++i)
18     inv[i]=(1ll*(p-(p/i))*inv[p%i])%p,printf("%d
",inv[i]);
19     return 0;
20 }