拓展欧几里得

陈子骏 · 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;
}