最快速题解 线性筛+素数性质| #kotori和素因子#

/*
首先用线性筛求出1000以内的质数（这里可以打表做到更快，但实在不必要）
然后求出每个数的所有因子，这一步有很多可以优化的地方。1.先看本身是不是素数，2.将已知素数从小向大比较，3.如果是因子，在计入的同时，还要让这个数本身除掉这个因子（如果是多重还可以除多次）。
然后是深搜过程，这里用到一个特性：素数作为因子是唯一的，当我们要用到一个素数时，在总乘积中乘以这个素数，再想用这个素数就会发现乘积中已经存在，则不可使用。换句话说，就是用乘法，省去了 !use.count(prim) 的比较过程。
在深搜中还有一步剪枝，如果现在的和已经大于了最小值，就把这个枝减掉，免去无意义的计算。
这个方法应该把每一步都优化到极限了，如果还有更优解欢迎回复。
*/

#include <vector>
#include <iostream>

#define N 1000

using namespace std;

vector<int> prime;
bool mark[N+5];
vector<int> factor[12];
int n, MinSum=2147483647;

void getPrime() { //线性筛法求素数
    for(int i=2; i<=N; i++) {
        if(!mark[i]) prime.push_back(i);
        for(int num : prime) {
            if(num * i > N) break;
            mark[num*i] = 1;
            if(i % num == 0) break;
        }
    }
}

void dfs(int i, long long mul, int sum) {
    if(sum > MinSum) return; //剪枝
    if(i>=n) {
        if(sum < MinSum) MinSum = sum;
        return;
    }

    for(int num: factor[i]) {
        if(mul%num != 0) dfs(i+1, mul*num, sum+num); //余数为0说明没被使用过，然后就在乘积中乘以
    }
}

int main() {
    getPrime();
    int num;
    cin >> n;
    for(int i=0; i<n ;i++) {
        scanf("%d", &num);
        if(!mark[num]) { //如果本身是素数则直接结束
            factor[i].push_back(num); 
            continue;
        }
        for(int p: prime) {
            if(p > num) break;
            if(num % p == 0) {
                factor[i].push_back(p);
                while(num % p == 0) num /= p; //快速得到因子
            }
        }
    }
    dfs(0, 1, 0);
    if(MinSum < 2147483647) 
        cout << MinSum << endl;
    else
        puts("-1");
    return 0;
}

首先用线性筛求出1000以内的质数（这里可以打表做到更快，但实在不必要）

然后求出每个数的所有因子，这一步有很多可以优化的地方。1.先看本身是不是素数，2.将已知素数从小向大比较，3.如果是因子，在计入的同时，还要让这个数本身除掉这个因子（如果是多重还可以除多次）。

然后是深搜过程，这里用到一个特性：素数作为因子是唯一的，当我们要用到一个素数时，在总乘积中乘以这个素数，再想用这个素数就会发现乘积中已经存在，则不可使用。换句话说，就是用乘法，省去了 !use.count(prim) 的比较过程。

在深搜中还有一步剪枝，如果现在的和已经大于了最小值，就把这个枝减掉，免去无意义的计算。

这个方法应该把每一步都优化到极限了，如果还有更优解欢迎回复。