85 lines
1.5 KiB
C
85 lines
1.5 KiB
C
#include <stdio.h>
|
|
#include <math.h>
|
|
|
|
#define LIM 3 * 1000000
|
|
#define MAX_CHAIN 100
|
|
|
|
void initf(int f[]);
|
|
void init_sieve(char s[], int len);
|
|
long next_term(long x, int f[]);
|
|
|
|
int main()
|
|
{
|
|
int x = pow(10, 6);
|
|
int y = 60;
|
|
int c, len, count;
|
|
long i, n;
|
|
long chain[MAX_CHAIN];
|
|
int f[10];
|
|
char sieve[LIM];
|
|
|
|
initf(f);
|
|
init_sieve(sieve, LIM);
|
|
count = 0;
|
|
|
|
for(i = 3; i < x; ++i){
|
|
c = len = 0;
|
|
n = i;
|
|
while(n >= LIM || !sieve[n]){
|
|
if(c < MAX_CHAIN){
|
|
chain[c] = n;
|
|
++len;
|
|
}
|
|
n = next_term(n, f);
|
|
++c;
|
|
}
|
|
c += sieve[n];
|
|
if(c == y){
|
|
++count;
|
|
}
|
|
for(n = 0; n < len; ++n){
|
|
if(chain[n] < LIM){
|
|
sieve[chain[n]] = c;
|
|
}
|
|
--c;
|
|
}
|
|
|
|
}
|
|
printf("%d\n", count);
|
|
return 0;
|
|
}
|
|
|
|
long next_term(long x, int f[])
|
|
{
|
|
long r;
|
|
int i, d;
|
|
r = 0;
|
|
for(i = pow(10, (int) log10(x)); i >= 1; i /= 10){
|
|
d = x / i;
|
|
r += f[d];
|
|
x -= d * i;
|
|
}
|
|
return r;
|
|
}
|
|
|
|
void initf(int f[])
|
|
{
|
|
int i;
|
|
f[0] = f[1] = 1;
|
|
for(i = 2; i < 10; ++i){
|
|
f[i] = i * f[i - 1];
|
|
}
|
|
}
|
|
|
|
void init_sieve(char s[], int len)
|
|
{
|
|
int i;
|
|
|
|
for(i = 0; i < len; ++i){
|
|
s[i] = 0;
|
|
}
|
|
s[1] = s[2] = s[145] = s[40585] = 1;
|
|
s[871] = s[45361] = s[872] = s[45362] = 2;
|
|
s[169] = s[363601] = s[1454] = 3;
|
|
}
|