线性递推求解逆元模板

1. #include <stdio.h>
2. #include <ctype.h>
3. #include <algorithm>
4. #include <string.h>
5. #define lnt long long
6. #define inf 0x3f3f3f3f
7. using namespace std;
8. int xx;char ff,chh;inline int read(){
9.     xx=ff=0;while(!isdigit(chh)){if(chh=='-'){ff=1;}chh=getchar();}
10.     while(isdigit(chh)){xx=(xx<<1)+(xx<<3)+chh-'0';chh=getchar();}return ff? -xx: xx;
11. }
12. const int N=1e7;
13. int inv[N];
14. int main(){
15.         inv[1]=1;
16.         int n=read(),mod=read();
17.         puts("1");
18.         for(int i=2;i<=n;++i){
19.                 inv[i]=(-(lnt)(mod/i)*inv[mod%i])%mod;
20.                 if(inv[i]<0){inv[i]+=mod;}
21.                 printf("%d\n",inv[i]);
22.         }
23.     return 0;
24. }

复制代码

                                   i                         n                         v                         [                         ]                              inv[]                  inv[] 即为逆元。推导下次再水喵。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。