UnKoder #05 B GCD and LCM

2015/05/20 (Wed) hackerrank UnKoder 数学

問題

問題文

方針

$ \gcd(x,y) = g, \lcm(x,y) = l $ とおくと $xy = gl$ となる．

実装

ll gcd(ll a, ll b) {
    return std::__gcd(a,b); // at algorithm
    // return b != 0 ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}
// ax+by = gcd(a,b)
ll extgcd(ll a, ll b, ll & x, ll & y) {
    ll g = a; x = 1; y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}

ll solve(ll a, ll g, ll l){
    if(g > l) return -1;
    if(a%g!=0 || l%a!=0) return -1;
    ll x = g*l/a;
    if(gcd(a,x)!=g || lcm(a,x)!=l) return -1;
    return x;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll a,g,l;
    cin >> a >> g >> l;
    cout << solve(a,g,l) << endl;
}