O(1) 的小樂

DIV2 1000

使用一個整數的所有素因子能否組成一個回文字符串？要求數出在A與B之間滿足要求的這樣的整數的數目。

暴力解決就OK，next_permutation 的復雜度要計算準確!不是簡單的數目的階乘！！

template<class T> string toString(T n){ostringstream ost;ost<<n;ost.flush();return ost.str();}
bool judge(string c)
{
    for(int i=0; i<=c.size()/2; i++)
    {
        if(c[i]!= c[c.size()-i-1]) return false;
    }
    return true;
}
bool func(int num)
{
    vector<string> p;
    int temp = num;
    for(int i=2; i*i<=num; i++)
    {
        while(temp % i==0)
        {
            p.push_back(toString(i));
            temp/=i;
        }
    }
    if(temp!=1) p.push_back(toString(temp));
    sort(p.begin(), p.end());
    do
    {
        string c;
        for(int i=0; i<p.size(); i++) c+=p[i];
        if(judge(c)){ for(int i=0; i<p.size(); i++) cout<<p[i]<<" "; cout<<endl; return true;}
    }while(next_permutation(p.begin(), p.end()));
    return false;
}
class PrimePalindromic
{
    public:
        int count(int A, int B)
        {
            int ret = 0;
            for(int i=A; i<=B; i++)
                if(func(i)){ cout<<" "<<i<<endl;  ret++;}
            return ret;
        }
};