SRM517 Div1 Easy CompositeSmash
問題
$ \newcommand{\lcm}[1]{\operatorname{lcm} #1} $ 2つの整数 $N$, $target$ が与えられる．以降それぞれ $x$,$y$ と呼ぶことにする． ある数 $n$ が合成数の場合，それをスマッシュするとランダムで $p,q$ に割れる． $p,q$ は $n$ の約数であり，$pq=n$ である．素数なら何も起こらない． $x$ から始めて，何度かのスマッシュを繰り返して必ず $y$ を作れるだろうか？
方針
整数論っぽい問題文だが実際はゲーム木探索のようなDP．
ある $x$ をスマッシュして $p,q$ に分かれたとすると，$p$ か $q$ のどちらかから始めて必ず
$y$ を作れるなら答えは Yes になる．
$x$ の全ての分かれ方に対してこの条件を満たせば，どんな分かれ方をしても大丈夫なので Yes．
1つでもだめな組があれば No．ゲームでよくあるメモ化探索で実装する．
実装
char dp[200000];
vector<int> EratosthenesSieve(int n){
vector<int> ps(n+1);
loop(i,2,n+1) ps[i] = i;
for (int i = 2; i*i <= n; ++i)
if (ps[i])
for (int j = i*i; j <= n; j+=i)
ps[j] = 0;
// ps.erase(remove(all(ps),0), ps.end());
return ps;
}
auto isp = EratosthenesSieve(100010);
class CompositeSmash {
public:
int x, y;
// x -> y
string thePossible(int x_, int y_) {
tie(x,y) = tie(x_,y_);
if(x%y != 0) return "No";
memset(dp,-1,sizeof dp);
return rec(x) ? "Yes" : "No";
}
bool rec(int k){
char & res = dp[k];
if(res != -1) return res;
if(k == y) res = true;
else if(isp[k]) res = false;
else {
res = true;
for(int i=2;i*i<=k;i++){
if(k%i==0 && !rec(k/i) && !rec(i)) res = false;
}
}
return res;
}
};
大学では試験が終わりました．果たして卒業は確定するのでしょうか…