SRM535 Div1 Easy(250) Div2 Medium(500) 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; }};