快速切题 sgu116. Index of superprime bfs+树思想

116. Index of super-prime

time limit per test: 0.25 sec. 
memory limit per test: 4096 KB

 

Let P₁, P₂, … ,P_N, … be a sequence of prime numbers. Super-prime number is such a prime number that its current number in prime numbers sequence is a prime number too. For example, 3 is a super-prime number, but 7 is not. Index of super-prime for number is 0 iff it is impossible to present it as a sum of few (maybe one) super-prime numbers, and if such presentation exists, index is equal to minimal number of items in such presentation. Your task is to find index of super-prime for given numbers and find optimal presentation as a sum of super-primes.

 

Input

There is a positive integer number in input. Number is not more than 10000.

 

Output

Write index I for given number as the first number in line. Write I super-primes numbers that are items in optimal presentation for given number. Write these I numbers in order of non-increasing.

 

Sample Input

6

Sample Output

2
3 3
用时:14min

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxnum=10001;
bool isntprime[maxnum];//是否质数
bool supp[maxnum];//是否superprime
int sup[300],pind;//把superprime放在一起
int ans[maxnum][2];//每个数必然=一个放在queue里的数+一个superprime,相当于记录路径
int vis[maxnum];//bfs记录状态
int n;
queue<int>que;
int bfs(){//找出当前数由那些超级质数构成,可以
    while(!que.empty()&&vis[n]==0){
        int tp=que.front();que.pop();
        for(int i=0;i<pind;i++){
            if(tp+sup[i]<=n&&vis[tp+sup[i]]==0){
                vis[tp+sup[i]]=vis[tp]+1;
                ans[tp+sup[i]][0]=sup[i];
                ans[tp+sup[i]][1]=tp;
                que.push(tp+sup[i]);
                if(tp+sup[i]==n)break;
            }
            else if(tp+sup[i]>n)break;
        }
    }
    return vis[n];
}

void calc(){//找出超级质数
    int cnt=1;
    for(int i=3;i<maxnum;i+=2){
        if(!isntprime[i]){
            cnt++;
            if(((cnt&1)!=0||cnt==2)&&!isntprime[cnt]){
                sup[pind++]=i;
                supp[i]=true;
                vis[i]=1;
                if(i<=n)que.push(i);
            }
            for(int j=3*i;j<maxnum;j+=2*i){
                isntprime[j]=true;
            }
        }
    }
}

int main(){
    scanf("%d",&n);
    calc();
    int num=bfs();
    if(num==0){
        puts("0");
    }
    else {
        printf("%d\n",vis[n]);
        int tn=n;
        while(!supp[tn]){
            printf("%d ",ans[tn][0]);
            tn=ans[tn][1];
        }
        printf("%d\n",tn);
    }
    return 0;
}