SRM534 Div1 Medium(500) EllysNumbers

EllysNumbers

n=xⁱy^jz^k… と表せるならば、有効な積の中で素因数xを含むspecialはちょうど1個。そこで、nを素数の冪の積に分解することを考える。例えば、n=360とすると、n=2³*3²*5 ではなく、n=8*9*5と分解する。こうすると、specialの要素の中から、素数の冪をそれぞれちょうど1個含むような組合わせを数える問題になる。nの範囲から素数の冪の個数は高々15個なので、ビットDPで解ける。

#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>
using namespace std;

class EllysNumbers{public:
long long getSubsets( long long n, vector <string> special )
{
    //  specialをvector<long long>にする
    vector<long long> sp;
    stringstream ss(accumulate(special.begin(),special.end(),string()));
    long long t;
    while(ss>>t)
        sp.push_back(t);

    //  nを素数の冪の積に分解する
    //  例: 360 = 8 * 9 * 5
    vector<long long> P;
    long long N = 100000;
    t = n;
    for ( int i=2; i<=N; i++ )
    if ( t%i==0 )
    {
        long long x = 1;
        while ( t%i==0 )
            t /= i,  x *= i;
        P.push_back(x);
    }
    for ( int i=0; i<(int)sp.size(); i++ )
        for ( long long j=min(N,sp[i]-1); j>=1; j-- )
        if ( sp[i]%j==0 && t%(sp[i]/j)==0 )
        {
            long long x = 1;
            while ( t%(sp[i]/j)==0 )
                t /= sp[i]/j,  x *= sp[i]/j;
            P.push_back(x);
        }
    //  ここでnの素因数が全て見つかっていないなら、答えは0
    if ( t!=1 )
        return 0;

    //  T[x]: P[i]を約数に含む数を掛けていれば、xのi番目のビットが1
    vector<long long> T(1<<P.size());
    T[0] = 1;
    
    for ( int i=0; i<(int)sp.size(); i++ )
    {
        vector<long long> B = T;
        T = vector<long long>(1<<P.size());
        
        int b = 0;
        long long t = sp[i];
        for ( int j=0; j<(int)P.size(); j++ )
            if ( t%P[j]==0 )
                t /= P[j],
                b |= 1<<j;

        for ( int j=0; j<1<<(int)P.size(); j++ )
        {
            //  sp[i]を掛けない
            T[j] += B[j];

            //  sp[i]を掛ける
            if ( (j&b)==0 && t==1 )
                T[j|b] += B[j];
        }
    }
    
    return T[(1<<P.size())-1];
}};