//埋め込み解 #include int main() { std::puts("urtynvwwtsgvkjpe"); std::puts("jxvjzjihihyfamvh"); } //以下、生成に使ったコード //1GBのメモリだけを使い、4分以下で生成できた #if 0 #include #include #include #include using namespace std; struct Xor128 { unsigned x, y, z, w; Xor128(): x(123456789), y(362436069), z(521288629), w(88675123) { } unsigned operator()() { unsigned t = x ^ (x << 11); x = y; y = z; z = w; return w = w ^ (w >> 19) ^ (t ^ (t >> 8)); } unsigned operator()(unsigned n) { return operator()() % n; } }; typedef unsigned long long ull; inline ull modmult(ull x, ull y, ull MOD) { unsigned long long a = x, r = 0; while(y) { if(y & 1) if((r += a) >= MOD) r -= MOD; if((a += a) >= MOD) a -= MOD; y >>= 1; } return r; } inline void modadd(ull &x, ull y, ull MOD) { if((x += y) >= MOD) x -= MOD; } __forceinline void increamentHash(ull &curHash, char curString[], ull coeffZA[], ull powers[], int N, ull P, Xor128 &xor128) { int incPos; do { incPos = xor128() & 0xf; } while(incPos >= N); for(int i = incPos; i < N; ++ i) { if(curString[i] ++ == 'z') { curString[i] = 'a'; modadd(curHash, coeffZA[i], P); } else { modadd(curHash, powers[i], P); break; } } } int main() { const ull P = 1000000000000000003ULL; const ull B = 123456789987654321ULL; const int TableBits = 28; const int N = 16; const int A = 26; assert(P < 1ULL << 63); assert(((P-1) >> TableBits) < (1ULL << 32)); unique_ptr table(new unsigned[size_t(1) << TableBits]); memset(table.get(), 0, sizeof(unsigned) << TableBits); ull powers[N]; powers[N - 1] = 1 % P; for(int i = N - 2; i >= 0; -- i) powers[i] = modmult(powers[i + 1], B, P); ull coeffZA[N]; for(int i = 0; i < N; ++ i) coeffZA[i] = (P - modmult(powers[i], 'z' - 'a', P)) % P; char curString[N+1]; ull initHash = 0; for(int i = 0; i < N; ++ i) { curString[i] = 'a'; modadd(initHash, modmult(powers[i], 'a', P), P); } curString[N] = 0; ull curHash = initHash; Xor128 xor128; char secondString[N+1]; ull targetHash; long long iter; size_t tableEntries = 0; for(iter = 0;; ++ iter) { if((iter & ((1U << 26) - 1)) == 0) fprintf(stderr, "iter = %lld, table = %lld\n", iter, (long long)tableEntries); unsigned tableIndex = curHash & ((1U << TableBits) - 1); unsigned tableValue = (unsigned)(curHash >> TableBits); unsigned t = table[tableIndex]; if(t == 0) { table[tableIndex] = tableValue; ++ tableEntries; } else if(t == tableValue) { printf("iter = %lld: %s, %llu\n", iter, curString, curHash); memcpy(secondString, curString, sizeof(curString)); targetHash = curHash; break; } increamentHash(curHash, curString, coeffZA, powers, N, P, xor128); } curHash = initHash; for(int i = 0; i < N; ++ i) curString[i] = 'a'; xor128 = Xor128(); for(iter = 0;; ++ iter) { if(curHash == targetHash) break; increamentHash(curHash, curString, coeffZA, powers, N, P, xor128); } printf("%s\n%s\n", curString, secondString); fprintf(stderr, "hash = %llu\n", curHash); return 0; } #endif