Uva 12218 An Industrial Spy－louisfghbvc的部落格

題目大意 : 問這個數字的排列，子集合共有幾個質數

思路: 建立質數表，暴力法，枚舉所有子集合，每枚舉一種子集合，就嘗試所有子集合排列組合。子集合枚舉方式可參考Leetcode subset那題。

有其他作法，雖然用2進位很潮。

代碼:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7;

bool np[N];
void init(){ // 歐式篩
    for(int i = 2; i <= sqrt(N); ++i){
        for(int j = 2*i; j < N; j += i)
            np[j] = 1;
    }
}

int main() {
    //cin.tie(0); ios::sync_with_stdio(false);
    init();
    int T;
    cin >> T;
    np[1] = np[0] = 1;
    for(int t = 0; t < T; ++t){
        string s;
        cin >> s;
        sort(s.begin(), s.end());

        set<int> res;
        for(int i = 1; i < 1<<s.size(); ++i){ // 枚舉所有subset，1取 0不取，e.g 001 表示第0個取。 第1,2個都不取

            string tmp = "";
            for(int j = 0; j < (int)s.size(); ++j){ // 這邊去看i有哪幾個是1，設1的要取。
                if(i>>j&1) tmp += s[j]; // 也可以寫成 if((1<<j) & i)
            }

            do{
                int num = stoi(tmp);
                if(np[num] || res.count(num)) continue;
                res.insert(num);
            }while(next_permutation(tmp.begin(), tmp.end()));

        }

        cout << res.size() << "\n";
    }
}
/**
4
17
1276543
9999999
011
**/