This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
$prime-palindromic$とは，素因数の並び替えで回文が作れることを言う．$A \sim B$に何個$prime-palindromic$があるか．
事前に10000までの数の素因数を出してみると少ないことが分かるので，愚直に全パターン並び替えを行って，連結して回文判定をした．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
vector < ll > prime_factor ( ll n ) {
vector < ll > res ;
if ( n == 1 ) return res ;
for ( ll i = 2 ; i * i <= n ; i ++ ) {
while ( n % i == 0 ) {
res . push_back ( i );
n /= i ;
}
}
if ( n != 1 ) res . push_back ( n );
return res ;
}
string f ( ll x ) {
string ret = "" ;
while ( x ) {
ret = char ( '0' + x % 10 ) + ret ;
x /= 10 ;
}
return ret ;
}
class PrimePalindromic {
public :
int count ( int A , int B ) {
int ans = 0 ;
REP ( i , A , B + 1 ) {
vector < ll > ret = prime_factor ( i );
sort ( ret . begin (), ret . end ());
do {
string s = "" ;
rep ( j , ret . size ()) s += f ( ret [ j ]);
bool flag = true ;
rep ( j , s . size () / 2 ) {
if ( s [ j ] == s [ s . size () - 1 - j ]) continue ;
flag = false ;
}
if ( flag ) {
ans ++ ;
break ;
}
} while ( next_permutation ( ret . begin (), ret . end ()));
}
return ans ;
}
};