这是一道水题：使用扩展欧几里得算法即可。
关于扩展欧几里得算法：
众所周知，欧几里得算法有这样的性质：gcd(a,b) = gcd(b,a mod b)；
而扩展欧几里得算法是用于解形如：ax+by = gcd(a,b) = k 的不定方程通解；
那么这样的通解存在且b∈N*时有：bx'+(a mod b) y' =gcd(a,b)同样有解；
由于 a mod b = a - [a/b]b，则原方程可化为：y'a+(x'-[a/b]y')b = gcd(a,b)；递归求解即可，复杂度O(log n)。
那么原题中方程ax≡1(mod b)由同余定义可以化为ax=1+by，即ax-by = 1，于是就成为了扩展欧几里得算法模板题= =
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
void extgcd(LL a,LL b,int &x,int &y){
if(!b){x = 1;y = 0;return;}
extgcd(b,a%b,x,y);
int tmp = x;x = y;y = tmp-(a/b)*y;
}
int main()
{
LL a,b;
int x,y;
scanf("%lld%lld",&a,&b);
extgcd(a,b,x,y);
x = (x % b + b) % b;
printf("%d\n",x);
return 0;
}
评论 (0)
