Problem 238

238 Infinite string tour

Problem 238 – Project Euler

とりあえず，問題サイズが大きい．

ポイントは乱数ではなく，疑似乱数である点かと．

あと，少しだけ見掛け倒しかも．

疑似乱数であることが重要．

まぁ，疑似乱数の生成式をみれば，循環する気マンマンであるが…

そこで，循環することを利用すると，ある数までの p(k) を求めれば良いことが分かる．

で，ふるいを使うアルゴリズムを当然考えるわけだが，最悪計算量が非常に大きい

(p(k)の値が非常に大きい場合，まぁ，そんなことはなさそうだが，ない根拠がなかった）．

そんな，こんな，で解けていなかったが，時間かかっても良いから解こうと思い，

C++で実装したら，思いのほか速く終了した．

p(k)は100を越えなかった．

#include <iostream>
#include <vector>
#include <stack>
#define FOR(x, xs) for (__typeof( (xs).begin() ) x = (xs).begin(); x != (xs).end(); x++)
using namespace std;
int main() {
const long long s0 = 14025256;
const long long m = 20300713;
const long long u = 2e15;
long long s = s0;
vector<int> w;
do {
int t = s;
stack<int> tmp;
while (t != ) {
tmp.push(t % 10);
t /= 10;
}
while (!tmp.empty()) {
w.push_back(tmp.top());
tmp.pop();
}
s = (s*s) % m;
} while (s != s0);
const int len = w.size();
int sum = ;
FOR (x, w) sum += *x;
vector<int> p(sum);
int c = ;
FOR(x, p) *x = ;
for (int i = ; i < len; i++) {
for (int j = , as = w[i]; j < len; as += w[ (++j + i) % len ] ) {
if (p[as] != ) continue;
p[as] = i+1;
if (++c > sum ) goto COUNT;
}
}
COUNT:
long long count = u / sum;
for (int x = 1; x < sum; x++)
count += p[x] * ( 1 + ( (u - x) / sum ) );
cout << count << endl;
}

C++で，はじめて，goto文を使った．goto文使ってはいけいない，みたいな話を聞くけど，そんなことはない，と思っている．

しかし，ラベル付きbreakが無いとは，知らなかった．

コンテンツ