kmjp's blog

競技プログラミング参加記です

UnKoder #05 : GCD and LCM

これは割と定番かな。
https://www.hackerrank.com/contests/unkoder-05/challenges/gcd-and-lcm

問題

整数A,D,Mが与えられる。
GCD(A,X)=DかつLCM(A,X)=MとなるXが存在すれば、それを答えよ。

解法

XはMの約数になるので、Mの約数を総当たりして条件を満たすものを答えればよい。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll A,D,M;
	cin>>A>>D>>M;
	set<ll> V;
	for(ll i=1;i*i<=M;i++) if(M%i==0) V.insert(i), V.insert(M/i);
	FORR(r,V) {
		if(__gcd(A,r)==D && A*r/__gcd(A,r)==M) return _P("%lld\n",r);
	}
	return _P("-1\n");
}

まとめ

ここまでは準備運動。