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 != 0) {
      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 = 0;
  FOR (x, w) sum += *x;

  vector<int> p(sum);
  int c = 0;
  FOR(x, p) *x = 0;
  for (int i = 0; i < len; i++) {
    for (int j = 0, as = w[i]; j < len; as += w[ (++j + i) % len ] ) {
      if (p[as] != 0) 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が無いとは，知らなかった．