SRM 517 Div2 Medium CompositeSmash

xが与えられた時,yz = xとなるような(y, z)に分割することができる.
分割できたy, zを選択して同様の操作を行うとする.
xとtragetが与えられた時この操作で必ずtargetを得ることができるのかを判定する問題.
・どのような(y, z)に分割するかは選択できない
・(y, z)のうちどちらを更に分割するかは選ぶことができる.

まずxとtargetの素因数分解をする.

x=a^p1
target = a^p2

の時p1 > p2かつp2<=2なら,分割した時に2以上の数を選択していけば必ずtargetを得ることができる.
またtargetが素数の時,xがtargetで割り切れるなら,分割した時にtargetを素因数に持つ方を選択していけば最終的にtargetを得ることができる.

class CompositeSmash
{
public:
  void primes(map<int, int> & m, int a){
    m.clear();
    int p = 2;
    while(a > 1 || p < a){
      for (;(a % p) == 0;){
        a /=p;
        if (m.find(p) != m.end()){
          m[p]++;
        }else{
          m[p] = 1;
        }
      }
      p++;
    }
  }
  string thePossible(int N, int target)
    {
      if (N < target) return "No";
      if (N == target) return "Yes";
      map<int, int> pn;
      map<int, int> pt;
      primes(pn, N);
      primes(pt, target);
      map<int, int>::iterator itrn;
      map<int, int>::iterator itrt;
      itrt = pt.begin();
      itrn = pn.begin();
      // cout << "itrn=(" << (*itrn).first << "," << (*itrn).second << endl;
      // cout << "itrn=(" << (*itrt).first << "," << (*itrt).second << endl;
      if((pt.size() == 1) && ((*itrt).second <= 2) && pn.size() == 1){
        if((*itrn).first == (*itrt).first &&
           (*itrn).second >= (*itrt).second) return "Yes";
      }else if((pt.size() == 1) && ((*itrt).second == 1)){
        for(itrn = pn.begin(); itrn != pn.end(); itrn++){
          if((*itrn).first == (*itrt).first) return "Yes";
        }
      }
      return "No";
    }
};