1 long long x,y,gcd; 2 void extend_gcd(long long a, long long b) 3 { 4 if(b == 0) 5 { 6 x = 1; 7 y = 0; 8 gcd = a; 9 } 10 else { 11 extend_gcd(b, a%b); 12 long long temp = x; 13 x = y; 14 y = temp - a/b*y; 15 } 16 }
为了保证求出的x是正整数，通常需要加上：x=(x%mod+mod)%mod
原文：http://www.cnblogs.com/ZP-Better/p/4659123.html