SRM302 div2 hard
div2hardの40問目。
メモ化再帰で解いた。ほとんど有り得ないけど、最悪O(100000*√100000)。
解説見るとBFS出来るらしい。値が減ることがないから。
#include <algorithm> using namespace std; int cache[100000+1]; class DivisorInc { public: int M; int rec(int num) { if(M<num) return (1<<28); if(cache[num]!=-1) return cache[num]; cache[num]=(1<<28); for(int i=2;i*i<=num;i++) if(num%i==0) { cache[num]=min(cache[num],1+rec(num+i)); cache[num]=min(cache[num],1+rec(num+num/i)); } return cache[num]; } int countOperations(int N, int _M) { M=_M; fill(&cache[0],&cache[100000],-1); cache[M]=0; int ans=rec(N); ans=((1<<28)<=ans) ? -1 : ans; return ans; } };