SRM535 Div1 Easy

250
LCM / GCD を素因数分解する。
あとは、各素数の累乗をどちらの数字に割り当てるかを全通り試す。
最初の素数20個の積がgoogle先生曰く5.5794083 × 10^26らしい。
問題の制約上、これで充分間に合う。

本番では、オーバーフローのことを考えていなかった。ツラい。

typedef long long lli;

lli gcd(lli a, lli b)
{
  return b ? gcd(b, a % b) : a;
}

class FoxAndGCDLCM {
public:
  long long get(const long long G, const long long L) 
  {
    if (L % G) return -1;
    
    const lli N = 1000005;
    bool prime[N];
    fill(prime, prime + N, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i*i < N; ++i) {
      for (int j = 2; i*j < N; ++j) {
        prime[i*j] = false;
      }
    }

    vector<lli> v;
    lli x = L / G;
    for (lli i = 0; i <= x && i < N; ++i) {      
      if (!prime[i]) continue;     
      if (x % i == 0) {
        lli y = 1;
        while (x % i == 0) {
          y *= i;
          x /= i;
        }
        v.push_back(y);
      }
    }
    if (x != 1) v.push_back(x);

    sort(v.begin(), v.end());
    vector<lli> cand;
    for (int i = 0; i < (1 << v.size()); ++i) {
      lli A = G, B = G;
      for (int j = 0; j < v.size(); ++j) {
        if (i & (1 << j)) A *= v[j];
        else B *= v[j];
      }
      if(gcd(min(A, B), max(A, B)) == G && 0 < A && 0 < B) cand.push_back(A + B);
    }

    return cand.size() ? *min_element(cand.begin(), cand.end()) : -1;
  }

};