SRM 517 DIV1 Easy - CompositeSmash （復習○）
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11535&rd=14542
正の整数Ｎとtargetが与えられる。
Ｎはスマッシュするとx*y=N（x,yは整数）となるｘとｙに分割することができる。
このとき、どうスマッシュしてもtargetが得られるならYes,得られないならNoを返す。
解き方
ＤＦＳで全探索。
１つの判定関数の中で全ての割り切れる数に対してtrueとなり、
かつ割り切れる数で得られるx,yのいずれかが判定関数でtrueとなるか判定する。
dp化しなければ計算量が超えそうかと思ったけど超えなかった。
こちらのソリューションでメモ化した方がよいかも。
http://community.topcoder.com/stat?c=problem_solution&cr=22263204&rd=14542&pm=11535
コード
int T;
class CompositeSmash {
public:
bool f(int N){
if(N==T)return true;
bool allfound=true,flag=false;
for(int i=2;i*i<=N;i++){
if(N%i==0){
flag=true;
allfound&=f(i)|f(N/i);
}
}
return flag ? allfound : false;
}
string thePossible(int N, int target) {
T=target;
return f(N) ?"Yes" : "No" ;
}
};
class CompositeSmash {
public:
bool f(int N){
if(N==T)return true;
bool allfound=true,flag=false;
for(int i=2;i*i<=N;i++){
if(N%i==0){
flag=true;
allfound&=f(i)|f(N/i);
}
}
return flag ? allfound : false;
}
string thePossible(int N, int target) {
T=target;
return f(N) ?"Yes" : "No" ;
}
};
using namespace std;
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[100001];
class CompositeSmash {
public:
string thePossible(int N, int target) {
memset(dp,0,sizeof(dp));
dp[target]=1;
for(int i=target+1;i<=N;i++){
int valid=1,flag=0;
for(int j=2;j*j<=i;j++){
if(i%j==0){
flag=1;
valid&=(dp[j]||dp[i/j]);
}
}
if(flag)dp[i]=valid;
}
return dp[N] ? "Yes" : "No";
}
};
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[100001];
class CompositeSmash {
public:
string thePossible(int N, int target) {
memset(dp,0,sizeof(dp));
dp[target]=1;
for(int i=target+1;i<=N;i++){
int valid=1,flag=0;
for(int j=2;j*j<=i;j++){
if(i%j==0){
flag=1;
valid&=(dp[j]||dp[i/j]);
}
}
if(flag)dp[i]=valid;
}
return dp[N] ? "Yes" : "No";
}
};
