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が無いとは,知らなかった.

More Reading
Newer// くらえ
Older// Problem 239