求模N下的乘法逆元

2019-04-13 20:42发布

站内文章 / 模拟电子
16298 0 972
逆元的定义：在群G中，任意一个元素a都有唯一一个逆元a^-1使得a*a^1 = e（e为群的单位元）。 在剩余系中，当a^-1存在时，“除以”一个数a等于乘它的逆元a^-1。 a*x = 1(modN); 其求法常见的有两种:扩展的欧几里得和欧拉定理; 扩展的欧几里得算法求乘法逆元: #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define MAX 1000 #define INF INT_MAX #define eps 1e-6 using namespace std; void ex_gcd(ll a, ll b, ll& d, ll& x, ll& y){ if (b == 0){ d = a; x = 1; y = 0; return; } ex_gcd(b,a%b,d,y,x); y -= x*(a / b); } ll inv(ll a, ll MOD){ ll d,x,y; ex_gcd(a,MOD,d,x,y); if (d == 1) return (x + MOD) % MOD; return -1LL; } int main(){ ll a, N; while (scanf("%lld%lld",&a,&N) != EOF){ printf("%lld ",inv(a,N)); } return 0; } 欧拉定理求逆元; 根据欧拉定理a^ϕ(N) = 1(mod N)（其中a与N互质），所以a在模N下的逆为a^(ϕ (n) - 1) 对N取模;
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define MAX 1000 #define INF INT_MAX #define eps 1e-6 using namespace std; int a,N; ll gcd(ll a, ll b){ if (b == 0) return a; return gcd(b, a%b); } ll mod_mul(ll a, ll b) //模N下的乘法运算 { long long ret = 0; while (b) { if (b & 1) ret = (ret + a) % N; a = 2 * a % N; b >>= 1; } return ret; } ll mod_pow(ll x, ll n) //模N下的幂运算 { long long ret = 1; x %= N; while (n) { if (n & 1) ret = mod_mul(ret, x); x = mod_mul(x, x); n >>= 1; } return ret; } ll oula(ll n) //求n的欧拉函数值 { ll i,res=1; for(i=2;i*i<=n;i++) { if(n%i==0) { n=n/i; res=res*(i-1); while(n%i==0) { n=n/i; res=res*i; } } if(n==1) break; } if(n>1) res=res*(n-1); return res; } int main(){ while (scanf("%lld%lld",&a,&N) != EOF){ if (gcd(a,N) != 1){ printf("-1 "); continue; } printf("%lld ",mod_pow(a, oula(N) - 1)); } return 0; }


热门文章