71 lines
2.2 KiB
C++
71 lines
2.2 KiB
C++
#include <cstdio>
|
|
#include <sstream>
|
|
#include <chrono>
|
|
|
|
using namespace std;
|
|
using namespace chrono;
|
|
|
|
struct LI { uint64_t a, b, c, d, e; }; const uint64_t Lm = 1e18;
|
|
auto st = steady_clock::now(); LI k[10][10];
|
|
|
|
string padZ(uint64_t x, int n = 18) { string r = to_string(x);
|
|
return string(max((int)(n - r.length()), 0), '0') + r; }
|
|
|
|
uint64_t ipow(uint64_t b, uint64_t e) { uint64_t r = 1;
|
|
while (e) { if (e & 1) r *= b; e >>= 1; b *= b; } return r; }
|
|
|
|
uint64_t fa(uint64_t x) { // factorial
|
|
uint64_t r = 1; while (x > 1) r *= x--; return r; }
|
|
|
|
void set(LI &d, uint64_t s) { // d = s
|
|
d.a = s; d.b = d.c = d.d = d.e = 0; }
|
|
|
|
void inc(LI &d, LI s) { // d += s
|
|
d.a += s.a; while (d.a >= Lm) { d.a -= Lm; d.b++; }
|
|
d.b += s.b; while (d.b >= Lm) { d.b -= Lm; d.c++; }
|
|
d.c += s.c; while (d.c >= Lm) { d.c -= Lm; d.d++; }
|
|
d.d += s.d; while (d.d >= Lm) { d.d -= Lm; d.e++; }
|
|
d.e += s.e;
|
|
}
|
|
|
|
string scale(uint32_t s, LI &x) { // multiplies x by s, converts to string
|
|
uint64_t A = x.a * s, B = x.b * s, C = x.c * s, D = x.d * s, E = x.e * s;
|
|
while (A >= Lm) { A -= Lm; B++; }
|
|
while (B >= Lm) { B -= Lm; C++; }
|
|
while (C >= Lm) { C -= Lm; D++; }
|
|
while (D >= Lm) { D -= Lm; E++; }
|
|
if (E > 0) return to_string(E) + padZ(D) + padZ(C) + padZ(B) + padZ(A);
|
|
if (D > 0) return to_string(D) + padZ(C) + padZ(B) + padZ(A);
|
|
if (C > 0) return to_string(C) + padZ(B) + padZ(A);
|
|
if (B > 0) return to_string(B) + padZ(A);
|
|
return to_string(A);
|
|
}
|
|
|
|
void fun(int d) {
|
|
auto m = k[d]; string s = string(d, '0' + d); printf("%d: ", d);
|
|
for (int i = d, c = 0; c < 10; i++) {
|
|
if (scale((uint32_t)d, m[0]).find(s) != string::npos) {
|
|
printf("%d ", i); ++c; }
|
|
for (int j = d, k = d - 1; j > 0; j = k--) inc(m[k], m[j]);
|
|
} printf("%ss\n", to_string(duration<double>(steady_clock::now() - st).count()).substr(0,5).c_str());
|
|
}
|
|
|
|
static void init() {
|
|
for (int v = 1; v < 10; v++) {
|
|
uint64_t f[v + 1], l[v + 1];
|
|
for (int j = 0; j <= v; j++) {
|
|
if (j == v) for (int y = 0; y <= v; y++)
|
|
set(k[v][y], v != y ? (uint64_t)f[y] : fa(v));
|
|
l[0] = f[0]; f[0] = ipow(j + 1, v);
|
|
for (int a = 0, b = 1; b <= v; a = b++) {
|
|
l[b] = f[b]; f[b] = f[a] - l[a];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
init();
|
|
for (int i = 2; i <= 9; i++) fun(i);
|
|
}
|