\(\qquad\!\!\)一些在求组合数的时候会很有用的东西:
1、乘法逆元:
\(\qquad\!\!\)当 \(p\) 为素数,\(a\) 为一个正整数且 \(a\) 与 \(p\) 互质,则 \(a^{-1}\equiv a^{p-2} \pmod{p}\)
\(\qquad\!\!\)例题:
\(\qquad\!\!\)给定 \(a\)、\(p\),保证 \(p\) 为素数并且 \(a\) 与 \(p\) 互质,求出在模 \(p\) 意义下的 \(a\) 的逆元。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| #include<bits/stdc++.h> #define in inline #define re register using namespace std; int a,p; in int qread() { int x=0,y=1; int ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') { y=-1; } ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*y; } in void qwrite(re int x) { if(x<0) { putchar('-'); qwrite(-x); } else { if(x>9) { qwrite(x/10); } putchar(x%10+'0'); } return ; } in int qpow(re int x,re int y) { int res=1; while(y) { if(y&1) { res=(res*x)%p; } x=(x*x)%p; y>>=1; } return res%p; } int main() { a=qread(); p=qread(); qwrite(qpow(a,p-2)); putchar('\n'); return 0; }
|