SRM535 Div1 Easy(250) Div2 Medium(500) FoxAndGCDLCM

FoxAndGCDLCM

A=aG, B=bG とすると、aとbは互いに素で、L=abG, A+B=(a+b)Gである。互いに素で積がL/Gとなる2個の整数の和で、最小のものを返せば良い。

#include <algorithm>
using namespace std;

long long gcd(long long a,long long b)
    {long long t;if(a>b)t=a,a=b,b=t;while(a)t=a,a=b%a,b=t;return b;}

class FoxAndGCDLCM{public:
long long get( long long G, long long L )
{
    if ( L%G!=0 )
        return -1;
    long long t = L/G;
    long long ans = t+1;
    for ( long long i=1; i*i<=t; i++ )
        if ( t%i==0 && gcd(i,t/i)==1 )
            ans = min( ans, i+t/i);
    return ans*G;
}};