模板：
int Extend_Euclid(int a, int b, int &x, int &y){
if(b == 0){
x = 1;
y = 0;
return a;
}
else{
int gcd,t;
gcd = Extend_Euclid(b, a%b, x, y);
t = x;
x = y;
y = t - (a / b) * y;
return gcd;
}
}
详见：http://www.cnblogs.com/yuelingzhi/archive/2011/08/13/2137582.html
hdu 2669
Sample Input
77 51
10 44
34 79
10 44
34 79
Sample Output
2 -3
sorry
7 -3
sorry
7 -3
求 a*x + b*y = 1。输出一个正数x，一个y。
直接套模板，最后对x < 0时处理一下，∵a*x + b*y = 1，所以x+=b，y-=a来保持值不变
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int N=100050; ll ex_gcd(ll a,ll b,ll &x,ll &y) //扩展欧几里德
{
if(b ==0)
{
x = 1;y = 0;
return a;
}
else
{
ll t = ex_gcd(b,a%b,y,x);
y = y - x*(a/b);
return t;
}
} int main()
{
ll a,b;
while(scanf("%I64d%I64d",&a,&b)!= EOF)
{
ll x,y;
ll tmp = ex_gcd(a,b,x,y);
if(1 % tmp)
printf("sorry\n");
else
{
while(x < 0){
x += b;
y -= a;
}
printf("%I64d %I64d\n",x,y);
}
}
return 0;
}
hdu 1576
Problem Description
要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
Input
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
2
1000 53
87 123456789
1000 53
87 123456789
Sample Output
7922
6060
6060
A % B = 0，A= Bx；
n = A%9973 , A = 9973y + n; Bx -9973y = n;
GCD(b,9973) = 1, b*x1 + 9973y1 = 1, b*x1*n + 9973 *(n*y1) = n
∴ x = n*x1, x1可以通多exGCD算出
最后的x通过 (x % MOD + MOD)%MOD 防止出现负数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int N=100050; void ex_gcd(int a,int b,int &x,int &y) //扩展欧几里德
{
if(b ==0)
{
x = 1;y = 0;
}
else
{
ex_gcd(b,a%b,y,x);
y = y - x*(a/b);
}
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,B;
scanf("%d%d",&n,&B);
int x,y;
ex_gcd(B,9973,x,y);
x *= n; printf("%d\n",(x%9973 + 9973)% 9973); //再加上一次，防止负
}
return 0;
}