素数 + 背包 - SGU 116. Index of super-prime

╰半夏微凉° 2022-03-30 04:14 148阅读 0赞

> # Index of super-prime    #

# [ *Problem's Link*][_Problem_s Link]    #

--------------------

**Mean:**

如果一个素数所在的位置还是素数，那么这个素数就是超级素数，比如3在第2位置，那么3就是超级素数.

现在给你一个数，求出来这个数由最少的超级素数的和组成，输出这个超级素数.

**analyse:**

很简单的完全背包，不需要二进制压缩，也不必考虑容量.

**Time complexity: O(N)**

**view code**

/\*\*  
 \* -----------------------------------------------------------------  
 \* Copyright (c) 2016 crazyacking.All rights reserved.  
 \* -----------------------------------------------------------------  
 \* Author: crazyacking  
 \* Date : 2016-01-08-10.51  
 \*/  
\#include <queue>  
\#include <cstdio>  
\#include <set>  
\#include <string>  
\#include <stack>  
\#include <cmath>  
\#include <climits>  
\#include <map>  
\#include <cstdlib>  
\#include <iostream>  
\#include <vector>  
\#include <algorithm>  
\#include <cstring>  
**using** **namespace** std;  
**typedef** **long** **long**( LL);  
**typedef** **unsigned** **long** **long**( ULL);  
**const** **double** eps( 1e-8);  
  
  
\#define REP( i, n ) \\  
 for ( int i = 0; i < (n); i++ )  
\#define FOR( i, b, e ) \\  
 for ( int i = (b); i <= (e); i++ )  
  
**const** **int**  
MAXN = 10001 ,  
oo = ( **int**) 1e9;  
  
**int** N;  
**int** cant;  
**int** from \[ MAXN \];  
**int** best \[ MAXN \];  
vector < **int** > SP;  
  
**int** prime( **int** x )  
\{   
**if** ( x < 2 ) **return** **false**;  
**if** ( x == 2 || x == 3 )  
**return** **true**;  
**if** ( x % 2 == 0 || x % 3 == 0 )  
**return** **false**;  
**for** ( **int** i = 6; ( i \- 1) \* ( i \- 1) <= x; i \+= 6 )  
**if** ( x % ( i \- 1) == 0 || x % ( i \+ 1) == 0)  
**return** **false**;  
**return** **true**;  
\}  
  
**int** main()  
\{   
  
scanf( "%d" , &N );  
FOR( i , 2 , N )  
**if** ( prime( i ) )  
\{   
cant \++;  
**if** ( prime( cant ) )  
SP . push\_back( i );  
\}  
  
//printf( "%d\\n", SP.size() );  
  
fill( best , best \+ N \+ 1 , oo );  
best \[ 0 \] = 0;  
REP( i , SP . size() )  
\{   
**int** val = SP \[ i \];  
FOR( j , val , N )  
**if** ( best \[ j \- val \] \+ 1 < best \[ j \] )  
\{   
best \[ j \] = best \[ j \- val \] \+ 1;  
from \[ j \] = i;  
\}  
\}  
  
**if** ( best \[N \] == oo )  
printf( "0 \\n " );  
**else**  
\{   
printf( "%d \\n " , best \[N \] );  
**int** val = N;  
**while** ( val > 0 )  
\{   
printf( "%d " , SP \[ from \[ val \] \] );  
val \-= SP \[ from \[ val \] \];  
\}  
printf( " \\n " );  
\}  
**return** 0;  
\}

[_Problem_s Link]: http://acm.sgu.ru/problem.php?contest=0&problem=116