拡張ユークリッドアルゴリズム解同余方程式(NOIP 2012)

    
(mod.cpp/c/pas)
【    】
    x       ax ≡ 1 (mod b)       。
【  】
      mod.in。
      ,        a, b,       。
【  】
      mod.out。
      ,        x 0 ,       。          。
【      】
mod.in 
3 10
mod.out
7
【    】
   40%   ,2 ≤b≤ 1,000;
   60%   ,2 ≤b≤ 50,000,000;
   100%   ,2 ≤a, b≤ 2,000,000,000。

#include <iostream>
#define ll long long
using namespace std;
ll a,b,x,y;
ll extended_gcd(ll  a,ll b,ll &x,ll &y)
{
    if (!b) { 
    	x=1; 
    	y=0; 
    	return a; 
    }
    else { 
    	ll ans=extended_gcd(b,a%b,x,y); 
        ll t=x; x=y; y=t-(a/b)*y;
        return ans;
    }
}
int main()
{
    cin>>a>>b;
    ll ans = extended_gcd(a, b, x, y);

    if (ans!=1) cout<<"No answer"<<endl;
    else
    {
        x=x%b;
        while (x<0) x+=b;
        cout <<x<<endl;
    }
    return 0;
}

// 3 10