kotori和素因子

C++ 解法, 执行用时: 2ms, 内存消耗: 384KB, 提交时间: 2021-09-07

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

int n;
int a[1010];//正整数的值
int mi=1e9;
//判断是否为质数
bool primer(int x){
   for(int i=2;i*i<=x;i++){
       if(x%i==0){
           return false;
       }
   }
    return true;
}
void dfs(int x,set<int> s,int temp){
    if(x==n){
        mi=min(mi,temp);
        return;
    }
    for(int i=2;i<=a[x];i++){
        if(a[x]%i==0 && primer(i)&&!s.count(i)){
            s.insert(i);
            dfs(x+1,s,temp+i);
            s.erase(i);
        }
    }
}
int  main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    set<int> s;
    dfs(0,s,0);
    if(mi==1e9)cout<<-1;
    else cout<<mi;
    return 0;
    
}

C++ 解法, 执行用时: 2ms, 内存消耗: 384KB, 提交时间: 2021-09-02

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1010],mi=1e9;
int f(int x){
    int i;
    for(i=2;i*i<=x;i++)if(x%i==0)return 0;
    return 1;
}

void dfs(int x,set<int>s,int temp){
    int i;
    if(x==n)mi=min(mi,temp);
    
    
    for(i=2;i<=a[x];i++){
        if(a[x]%i==0&&f(i)&&!s.count(i)){
            s.insert(i);
            dfs(x+1,s,temp+i);
            s.erase(i);
        }
    }
    /*for(i=2;i<=a[x];i++){
        if(a[x]%i==0&&f(i)&&!s.count(i)){
            s.insert(i);
            dfs(x+1,s,temp+i);
            s.erase(i);
        }
    }*/
}

int main(){
    cin>>n;
    int i;
    for(i=0;i<n;i++)cin>>a[i];
    set<int>s;
    dfs(0,s,0);
    if(mi==1e9)cout<<-1;
    else cout<<mi;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 408KB, 提交时间: 2021-10-03

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

int n;
int mi=1e9;
int a[1010];
int f(int x){
    int i;
    for(i=2;i*i<=x;i++)if(x%i==0)return 0;
    return 1;
}

void dfs(int x,set<int>s,int temp){
    int i;
    if(x==n)mi=min(mi,temp);                                    //要加if(x==n)这个判断
    for(i=2;i<=a[x];i++){                                          //我写成n了
        if(a[x]%i==0&&f(i)&&!s.count(i)){
            s.insert(i);
            dfs(x+1,s,temp+i);                     //我开始写的a[x+1]
            s.erase(i);
        }
    }
    
    
}


int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    set<int>s;
    dfs(0,s,0);
    if(mi==1e9){
        cout<<-1;

    }
    else cout<<mi;
    return 0;

}

C++ 解法, 执行用时: 2ms, 内存消耗: 464KB, 提交时间: 2021-11-22

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

ll value[10010];
ll n,mi = 1e9;

bool f1(ll x){
    for(int i = 2;i*i<=x;i++){
        if(x%i==0)return false;
    }
    return true;
}

void dfs(ll x,set<ll> nums,ll temp){
    if(x==n+1){
         mi = min(mi, temp);
        return;
    }
    for(int i = 2;i<=value[x];i++){ 
        if(value[x]%i==0&&f1(i)&&!nums.count(i)){
            nums.insert(i);
            dfs(x+1,nums,temp+i);
            nums.erase(i);
        }
    }
}
    
int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>value[i];
    }
    set<ll> nums;
    dfs(1,nums,0);
    if(mi==1e9)cout<<-1;
    else cout<<mi;
    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 284KB, 提交时间: 2022-04-05

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<limits.h>
int n;
int min = INT_MAX;

int judge(int a){
    if(a<2)return 0;
    for(int i=2;i*i<=a;i++){
        if(a%i == 0)return 0;
    }
    return 1;
}

void dfs(int* nums,int* primes,int index,int count){
    if(index == n){
        if(count<min)min = count;
        return;
    }
    int dup_flag = 0;
    for(int i=2;i<=nums[index];i++){
        if(nums[index]%i == 0 && judge(i)){//是素因子
            for(int j=0;j<index;j++){
                if(primes[j] == i){//已经选取了这个素数
                    dup_flag = 1;
                    break;
                }
            }
            if(dup_flag){//已经选取了这个素数
                dup_flag = 0;
                continue;
            }
            else{
                primes[index] = i;
                dfs(nums,primes,index+1,count+i);
                primes[index] = 0;
            }
            dup_flag = 0;
        }
    }
}

int main(){
    scanf("%d",&n);
    int* nums = (int*)calloc(n,sizeof(int));
    int* primes = (int*)calloc(n,sizeof(int));
    for(int i=0;i<n;i++)scanf("%d",&nums[i]);
    
    dfs(nums,primes,0,0);
    
    if(min<INT_MAX)printf("%d",min);
    else printf("%d",-1);
    free(nums);
    return 0;
}

详情