SRM517 Div1 Easy - CompositeSmash
問題
数字nが書かれたボールを殴ると、nが合成数であるとき、dとn/dが書かれた2つのボールに分裂する(d:ランダムなnの約数)
合成数でないときは何も起こらない
何度でもボールを殴れるとき、数字tが書かれたボールを必ず作ることができるかを判定
解法
t=nならもちろんYes
tがnの素因数ならボールを永遠に殴ってればいつか絶対tになるからYes
あとサンプル1みたいにnの素因数が1種類(=pとする)しかなく、n>=p*pかつt=p*pのときもYesになる
それ以外はNo
class CompositeSmash { public: vector<int> pf(ll n) { vector<int> res; for (ll i = 2; i*i <= n; i++) { while (n%i==0) { res.push_back(i); n /= i; } } if (n!=1) res.push_back(n); res.erase(unique(all(res)), res.end()); return res; } string thePossible(int n, int t) { vector<int> p = pf(n); if (n==t || count(all(p),t) || (p.size()==1 && p[0]*p[0]<=n && t==p[0]*p[0])) return "Yes"; return "No"; } };