求模乘法逆元

2019-04-13 12:03发布

站内文章 / 模拟电子
15969 0 1753

1.当gcd(a, b) = 1, 求（1/a）%b的值，相当求于 a*x = 1 (mod b)，等价于 （1） 1%b = (1 - y*b ) % b  =（a * x ）%b  = 1,所以ax =1 - by，即ax + by = 1;
2.当gcd(a, b) != 1时，因为a%b == gcd(a, b) * ((a / gcd(a, b)) % (b / gcd(a, b)))
所以(1%b) !=（a*x） %b,  但是(1%b) ==((a*x） %b) /gcd(a, b))，所以 (gcd(a, b)%b) ==(a*x） % b) 即ax + by = gcd(a, b);
代码如下： typedef long long LL ; LL exgcd(LL a,LL b,LL &x,LL &y){ if( b == 0 ) { x = 1; y = 0; return a; } else{ LL x1,y1; LL d = exgcd ( b , a % b , x1 , y1 ); x = y1; y= x1 - a / b * y1; return d; } }

实列：poj1061 #include using namespace std; typedef __int64 LL ; LL exgcd(LL a,LL b,LL &x,LL &y){ if( b == 0 ) { x = 1; y = 0; return a; } else{ LL x1,y1; LL d = exgcd ( b , a % b , x1 , y1 ); x = y1; y= x1 - a / b * y1; return d; } } int main() { LL x , y , m , n , l ; scanf("%I64d%I64d%I64d%I64d%I64d" , & x , & y , & m , & n , & l ); LL mn , r ; mn = m - n ; r = y - x ; if ( mn < 0 ) mn = - mn , r = -r ; LL rmn , rl ;//reverse 逆元 LL d = exgcd ( mn , l , rmn , rl ) ;// d = gcd( mn , l ) if ( r % d != 0 ) cout<<"Impossible"; else{ rmn *= ( r / d ) ; __int64 T = l / d ; printf( "%I64d" , ( rmn % T + T ) % T ) ; } return 0; }


热门文章