扩展欧几里得算法
输入样例
2
4 6
8 18
输出样例
-1 1
-2 1
代码
#include<iostream>
using namespace std;
typedef long long LL;
int exgcd(int a, int b, int& x, int& y)
{
/* 求解gcd(a,b),结束条件为b=0 */
if (b == 0)//0和a的最小公约数为a
{
x = 1;
y = 0;
return a;
}
/*回溯过程*/
int d = exgcd(b, a % b, y, x);// ax + b ( y - a / b * x)= d
y -= a / b * x;
return d;// d是最大公约数
}
int main()
{
int n;
scanf("%d", &n);
while (n--)
{
int a, b, x, y;
scanf("%d%d", &a, &b);
exgcd(a, b, x, y);
printf("%d %d\n", x, y);
}
return 0;
}
线性同余方程(乘法逆元)
输入样例
2
2 3 6
4 3 5
输出样例
impossible
-3
代码
#include<iostream>
using namespace std;
typedef long long LL;
int exgcd(int a, int b, int& x, int& y)
{
/* 求解gcd(a,b),结束条件为b=0 */
if (b == 0)//0和a的最小公约数为a
{
x = 1;
y = 0;
return a;
}
/*回溯过程*/
int d = exgcd(b, a % b, y, x);// ax + b ( y - a / b * x)= d
y -= a / b * x;
return d;// d是最大公约数
}
int main()
{
int n;
scanf("%d", &n);
while (n--)
{
int a, b, x, y, m;
scanf("%d%d%d", &a, &b, &m);
int d=exgcd(a, m, x, y);//线性同余方程等价于ax+my=b
if (b % d != 0)//如果b不是d的倍数,则无解
printf("impossible\n");
else
printf("%d\n", (LL)x * (b / d) % m);
}
return 0;
}