SRM535 DIV2 -Level2

<問題>
①整数GとLが与えられる。
②最大公約数がG,かつ最小公倍数がLである2つの数字の場合の数を返す。
 存在しない場合はー1を返す。

<解き方>
2つの数字がX、Yとすると、X*Y=G*Lとなる。
このままではGとLともに10^12と膨大な数のため計算式を工夫する。

次に、X=a*Gとなるa, Y=b*Gとなるbが必ず存在する。
ここで、
(a*G)*(b*G)=G*L
つまりa*b=L/Gとなるaとbが必ず存在する。
また、最大公約数がGであることから、aとbは互いに素でないといけない。
これによりO(10^6)で計算可能となる。

まとめると、
a*b=L/G かつ aとbは互いに素=最大公約数が1 となる全てのaとbを求めればよい。
そして裏を返すと、LがGで割り切れない場合は-1を返す。

<コード>
class FoxAndGCDLCM {

public:
long long gcd(long long a,long long b){

while(b!=0){
long long c=b;
b=a%b;
a=c;
}
return a;
}

long long get(long long G, long long L) {
long long ab=L/G,ret=-1;
if(L%G!=0)return -1;

for(long long a=1;a<=ab/a;a++){
if(ab%a==0 && gcd(a,ab/a)==1){
if(ret==-1)ret=G*(a+ab/a);
else ret=min(ret,G*(a+ab/a));
}
}
return ret;
}

};

このエントリーをはてなブックマークに追加