これは割と定番かな。
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"); }
まとめ
ここまでは準備運動。