47 lines
774 B
C
47 lines
774 B
C
#include <stdio.h>
|
|
|
|
typedef unsigned long long ull;
|
|
|
|
int is89(int x)
|
|
{
|
|
while (1) {
|
|
int s = 0;
|
|
do s += (x%10)*(x%10); while ((x /= 10));
|
|
|
|
if (s == 89) return 1;
|
|
if (s == 1) return 0;
|
|
x = s;
|
|
}
|
|
}
|
|
|
|
|
|
int main(void)
|
|
{
|
|
// array bounds is sort of random here, it's big enough for 64bit unsigned.
|
|
ull sums[32*81 + 1] = {1, 0};
|
|
|
|
for (int n = 1; ; n++) {
|
|
for (int i = n*81; i; i--) {
|
|
for (int j = 1; j < 10; j++) {
|
|
int s = j*j;
|
|
if (s > i) break;
|
|
sums[i] += sums[i-s];
|
|
}
|
|
}
|
|
|
|
ull count89 = 0;
|
|
for (int i = 1; i < n*81 + 1; i++) {
|
|
if (!is89(i)) continue;
|
|
|
|
if (sums[i] > ~0ULL - count89) {
|
|
printf("counter overflow for 10^%d\n", n);
|
|
return 0;
|
|
}
|
|
count89 += sums[i];
|
|
}
|
|
|
|
printf("1->10^%d: %llu\n", n, count89);
|
|
}
|
|
|
|
return 0;
|
|
}
|