noip2012同余(扩展欧几里得定理）

实质是 ax + by = 1；

gcd(a,b)=gcd(b,a mod b)---欧几里得算法；

//我的代码

#include <iostream>
using namespace std;
long long a,b,x,y,k;
void exgcd(long long a,long long b)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b);
k=x;
x=y;
y=k-a/b*y;
return;
}
int main()
{
cin>>a>>b;
exgcd(a,b);
cout<<(x%b+b)%b;
return 0;
}

//std代码

#include<iostream>
using namespace std;
long long a,b,x,y;
void exgcd(long long a,long long b,long long &x,long long &y)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b,x,y);
int z=x;
x=y;
y=z-y*(a/b);
}
int main()
{
cin>>a>>b;
exgcd(a,b,x,y);
cout<<(x%b+b)%b<<endl;
}