SRM 535 Div2 Medium FoxAndGCDLCM

提出したコードはTLEになるケースが有った

問題

整数AとBがあって,その最大公約数Gと最小公倍数Lが与えられる.
もし,GとLを満たすAとBがあるなら,A+Bが最小を求めよ.

解答

G/Lの因数を互いに素になるようにA, Bに振り分け最小を求めるところまでは分かった.
最初にGとLの因数を求めようとしたのが間違い.long longなのでべらぼうに時間が掛かる.
以下TLEになるコード.

class FoxAndGCDLCM
{
public:
  void getPrime(long long a, map<long long, int> & primes){
    cout << "a=" << a << endl;
    if (a % 2 == 0){
      primes[2] = 0;
      for(; a % 2 == 0; a /= 2)primes[2]++;
      cout << "i=" << 2 << " num=" << primes[2] << endl;
    }
    for(long long i = 3; i <= a; i+=2){
      if (a % i == 0){
        primes[i] = 0;
        for(; a % i == 0; a /= i)primes[i]++;
        // cout << "i=" << i << " num=" << primes[i] << endl;
      }
    }
  }
  long long get(long long G, long long L)
    {
      map<long long, int> pg;
      map<long long, int> pl;
      getPrime(G, pg);
      getPrime(L, pl);
      map<long long, int>::iterator itr, itr2;
      vector<long long> factors;
      for(itr = pg.begin(); itr != pg.end(); itr++){
        itr2 = pl.find(itr->first);
        if (itr2 == pl.end() || itr->second > itr2->second){
          return -1;
        }
        // for(int i = 0; i < (itr2->second - itr->second); i++) factors.push_back(itr->first);
        itr2->second -= itr->second;
      }
      long long res = LLONG_MAX;
      vector<int> num_factor;
      for(itr = pl.begin(); itr != pl.end(); itr++){
        if (itr->second > 0) {
          factors.push_back(itr->first);
          num_factor.push_back(itr->second);
        }
        // for(int i = 0; i < itr->second; i++) factors.push_back(itr->first);
      }
      cout << "factors ";
      for(int i = 0; i < factors.size(); i++) cout << factors[i] << ", ";
      cout << endl;
      // long long res = 1 << (sizeof(long long) -1);
      for(long long i = 0; i < (1<<factors.size()); i++){
        long long A = G;
        long long B = G;
        for(int j = 0; j < factors.size(); j++){
          long long v = 1;
          for(int k = 0; k < num_factor[j]; k++) v *= factors[j];
          if ((i >> j) & 1) A *= v;
          else B *= v;
        }
        // if (A+B < res)
        //   cout << "A=" << A << " B=" << B << " A+B="<< A+B << endl;
        res = min(res, A+B);
      }
      return res;
    }
};

美しい解答はこちらSRM535 Div1 Easy(250) Div2 Medium(500) FoxAndGCDLCM - 赤コーダーになりたい