逆元(个人模版)

逆元:

 1 int ex_gcd(int a,int b,int &x,int &y)    
 2 {    
 3     if(b==0)    
 4     {    
 5         x=1;    
 6         y=0;    
 7         return a;    
 8     }    
 9     int ans=ex_gcd(b,a%b,x,y);    
10     int tmp=x;    
11     x=y;    
12     y=tmp-a/b*y;    
13     return ans;    
14 }    
15 int mod_inverse(int a,int m)  
16 {  
17     int x,y;  
18     ex_gcd(a,m,x,y);  
19     return (x%m+m)%m;//如果直接求解出来的x是一个负数,那么显然我们要将其转化成正数。  
20 }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ex_gcd(个人模版)

    ex_gcd: 1 #include<stdio.h> 2 #include<string.h> 3 using namespace std; 4 in...

    Angel_Kitty
  • BZOJ 1083: [SCOI2005]繁忙的都市【Kruscal最小生成树裸题】

    1083: [SCOI2005]繁忙的都市 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2925  Sol...

    Angel_Kitty
  • POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

    Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

    Angel_Kitty
  • 经典算法学习之回溯法

    回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。  若用回溯法求问题的所有解时,要回溯到根,且根结点的所...

    用户1215536
  • BZOJ4269: 再见Xor(线性基)

    给定N个数,你可以在这些数中任意选一些数出来,每个数可以选任意多次,试求出你能选出的数的异或和的最大值和严格次大值。

    attack
  • ex_gcd(个人模版)

    ex_gcd: 1 #include<stdio.h> 2 #include<string.h> 3 using namespace std; 4 in...

    Angel_Kitty
  • 【leetcode】N-Queens II

    Now, instead outputting board configurations, return the total number of distinc...

    阳光岛主
  • HDU-2588-GCD

    ACM模版 描述 ? 题解 image.png 代码 #include <stdio.h> #include <math.h> int Euler(int n...

    f_zyj
  • LeetCode 201. Bitwise AND of Numbers Range(位运算)

    题意:给你两个数n,m 0<= n<=m <=2^31-1 ,让你计算从n到m的每个数依次位与的结果。

    ShenduCC
  • codechef QCHEF(不删除莫队)

    \(max |x − y| : L_i ≤ x, y ≤ R_i and A_x = A_y\)

    attack

扫码关注云+社区

领取腾讯云代金券