問題
http://community.topcoder.com/stat?c=problem_statement&pm=11787&rd=14727
エリーが好きな数であるｎが存在する。
ここで、複数の数が与えられ、その中から任意の数選んだ数字の積がｎになるようにしたい。
ただし、選んだ数字それぞれは約数を持たない数でなければいけない。
このとき、選んだ数字の積がｎとなる選び方の場合の数を求める。
解き方
問題文で最初見落としたが重要なところは、選んだ数字それぞれは約数を持たない数であるということ。
つまり、N=x^i * y^j *z^k で表わせるとき、
x,y,zではなく、x^i , y^j , z^kを最小単位の固まりとして考えることができる。
記を最小単位の固まりとして考えるとき、
与えられた数字xはnで割り切れ、かつn/xはxとの最大公約数が１でなければならない。
これに従って、まずは候補の数字を洗い出す。
次に、洗い出した候補の数字に対して最大公約数で割っていき、１にならなければ答えが存在しないので０を返す。
ここで洗い出した候補の数字に対して、その素因数がｎの素因数でもあるので
どの素因数からなるかのビットマスクを作成する。
ビットマスクを作成後、ｄｐを回してすべてのビットマスクが１となるものが答えとなる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#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()
class EllysNumbers {
public:
long long gcd(long long x,long long y){
return y ? gcd(y,x%y) : x;
}
long long getSubsets(long long n, vector<string> special) {
vector<long long> p,p2;
stringstream out(accumulate(all(special),string()));
long long x;
while(out>>x){
if(n%x==0&&gcd(n/x,x)==1)p.push_back(x);
}
x=n;
FORE(i,0,p.size())x/=gcd(x,p[i]);
if(x!=1)return 0;
map<int,int> mp;
int m=0;
int mask[500]={};
FORE(i,0,p.size()){
x=p[i];
for(int k=2;k*k<=x;k++){
if(x%k==0){
while(x%k==0)x/=k;
if(mp.find(k)==mp.end())mp[k]=m++;
mask[i]+=(1<<mp[k]);
}
}
if(x!=1){
if(mp.find(x)==mp.end())mp[x]=m++;
mask[i]+=(1<<mp[x]);
}
}
long long dp[1<<15];
memset(dp,0,sizeof(dp));
dp[0]=1;
FORE(i,0,p.size()){
for(int j=(1<<m)-1;j>=0;j--)if((j&mask[i])==0)dp[j+mask[i]]+=dp[j];
}
return dp[(1<<m)-1];
}
};
#define all(c) (c).begin(),(c).end()
#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()
class EllysNumbers {
public:
long long gcd(long long x,long long y){
return y ? gcd(y,x%y) : x;
}
long long getSubsets(long long n, vector<string> special) {
vector<long long> p,p2;
stringstream out(accumulate(all(special),string()));
long long x;
while(out>>x){
if(n%x==0&&gcd(n/x,x)==1)p.push_back(x);
}
x=n;
FORE(i,0,p.size())x/=gcd(x,p[i]);
if(x!=1)return 0;
map<int,int> mp;
int m=0;
int mask[500]={};
FORE(i,0,p.size()){
x=p[i];
for(int k=2;k*k<=x;k++){
if(x%k==0){
while(x%k==0)x/=k;
if(mp.find(k)==mp.end())mp[k]=m++;
mask[i]+=(1<<mp[k]);
}
}
if(x!=1){
if(mp.find(x)==mp.end())mp[x]=m++;
mask[i]+=(1<<mp[x]);
}
}
long long dp[1<<15];
memset(dp,0,sizeof(dp));
dp[0]=1;
FORE(i,0,p.size()){
for(int j=(1<<m)-1;j>=0;j--)if((j&mask[i])==0)dp[j+mask[i]]+=dp[j];
}
return dp[(1<<m)-1];
}
};