题解 | kotori和素因子

记录一下屎山代码。

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 1005;
int prime[maxn], pNum = 0;
bool p[maxn] = {0}, vis[maxn] = {false};
int a[maxn];
int n, MIN = 100000000;

void findPrime(){ // 求maxn以内的素数
    for(int i=2; i<maxn; i++){
        if(p[i] == false){
            prime[pNum++] = i;
            for(int j=i+i; j<maxn; j+=i){
                p[j] = true;
            }
        }
    }
}

struct factor{
    int x, cnt;
    factor():x(0), cnt(0){}
};

void fenjie(int a, factor fac[], int &num){ // 质因子分解，将a的所有质因子保存在fac中
    int sqr = (int)sqrt(1.0*a);
    for(int i=0; prime[i]<=sqr; i++){
        if(a % prime[i] == 0){
            fac[num].x = prime[i];
            while(a % prime[i] == 0){
                fac[num].cnt++;
                a /= prime[i];
            }
            num++;
        }
        if(a == 1)  break;
    }
    if(a != 1){
        fac[num].x = a;
        fac[num++].cnt = 1;
    }
}

void dfs(vector<vector<int> > v, int cnt, int sum){ // v记录了每个数的所有质因子
    if(cnt == n){
        if(sum < MIN){
            MIN = sum;
        }
        return;
    }
    for(int i=0; i<v[cnt].size(); i++){
        if(vis[v[cnt][i]] == false){
            vis[v[cnt][i]] = true;
            dfs(v, cnt+1, sum+v[cnt][i]);
            vis[v[cnt][i]] = false;
        }
    }
}


int main() {
    findPrime();
    cin >> n;
    vector<vector<int> > v(n+1);
    for(int i=0; i<n; i++){
        cin >> a[i];
        int num = 0;
        factor fac[10];
        fenjie(a[i], fac, num);
        for(int j=0; j<num; j++){
            v[i].push_back(fac[j].x);
        }
    }
    vector<int> ans;
    dfs(v, 0, 0);
    if(MIN == 100000000){
        cout << -1 << endl;
    }else{
        cout << MIN;
    }
}
// 64 位输出请用 printf("%lld")