拓展欧几里得
陈子骏
2018-09-24 20:22:26
```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=1;
y=0;
return a;
}
ll ans=exgcd(b,a%b,x,y);
ll temp=x;
x=y;
y=temp-a/b*y;
return ans;
}
ll cal(ll a,ll b,ll c)
{
ll x,y;
ll d = gcd(a,b,x,y);
if(c % d !=0 )return -1;
x * = (d/c);
b / = d;
if(b < 0) b = -b;
ll ans = x % b;
if(ans < 0)ans+=b;
return ans;
}
```