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;
}