hdu:Romantic（exgcd）
数学-扩展欧
直接打扩展欧的板子，注意ax+by=1。若x<0，让x+=b,y-=a，等式不变
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1,y=0;return a;
}
ll d=exgcd(b,a%b,x,y);
ll tmp=x;
x=y;
y=tmp-a/b*y;
return d;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll a,b;
while(cin>>a>>b)
{
ll x,y;
ll d=exgcd(a,b,x,y);
while(x<0) x+=b,y-=a;
if(d!=1) cout<<"sorry"<<'\n';
else cout<<x<<' '<<y<<'\n';
}
}