問題 156 の改良

力技で問いた結果のログから規則性を調べて改良してみました。
前よりは格段に速いですが、計算で求めてはいないので、
めちゃくちゃ速いというわけでは無いです。

#include <iostream>
#include <math.h>

using namespace std;

void f(unsigned long long n, unsigned long long sum[])
{
  for (unsigned long long i = n; i > 0; i /= 10)
  {
    unsigned long long k = i % 10;

    // 0 の桁は数えない
    if (k > 0)
    {
      sum[k]++;
    }
  }
}

int main(int argc, char *args[])
{
  const unsigned long long ten_billion = 10000000000ULL;
  unsigned long long total = 0;
  unsigned long long pattern[10][500];
  int pidx[10];
  unsigned long long sum[10];

  for (int d = 0; d < 10; d++)
  {
    sum[d] = 0;
    pidx[d] = 0;
    for (int i = 0; i < 500; i++)
    {
      pattern[d][i] = 0;
    }
  }
  
  for (unsigned long long n = 1; n <= ten_billion; n++)
  {
    f(n, sum);

    // d = 1 のものは total に加算
    if (n <= 1111111110ULL && n == sum[1])
    {
      total += n;
      // cout << "[N]d=1" << " n=" << n << " total=" << total << endl;
    }

    for (int d = 2; d <= 9; d++)
    {
      // 出現パターンを記録する(total には加算しない)
      if (n == sum[d])
      {
        // cout << "[P]d=" << d << " n=" << n << " total=" << total << endl;
        pattern[d][pidx[d]] = n;
        pidx[d]++;
      }
    }
  }

  // 見つけたパターンを元に 100 億増し毎に total へ加算
  for (unsigned long long d = 2; d <= 9; d++)
  {
    for (int i = 0; pattern[d][i] > 0; i++)
    {
      for (unsigned long long n = 0; n * ten_billion + pattern[d][i] < d * ten_billion; n++)
      {
        // cout << "ADD d=" << d << " val=" << n * ten_billion + pattern[d][i] << endl;
        total += n * ten_billion + pattern[d][i];
      }
    }
  }

  cout << "total= " << total << endl;
  return 0;
}

事務所 PC は遅くて使い物になりませんが、仕事用 Linux マシン (CentOS)があったので、こいつの Docker コンテナ内でこっそり作業していましたｗ
64ビットマシンなのでそれなりですが性能はいまいちです。同じ処理で 4 分ぐらいかかります。

結果

$ time ./problem-156
total= 21295121502550

real	2m55.890s
user	2m55.828s
sys	0m0.015s