Project Euler - Problem 303

タスクが積まれて鬱が加速している

Multiples with small digits

正の整数 $n$ に対し，各桁の数字が $2$ 以下である $n$ の倍数で最小のものを $f(n)$ とする．

したがって，$f(2) = 2, \ f(3) = 12, \ f(7) = 21, \ f(42) = 210, \ f(89) = 1121222.$

また，$\displaystyle \sum_{n = 1}^{100} \frac{ f(n) }{ n } = 11363107.$

$\displaystyle \sum_{n = 1}^{10000} \frac{ f(n) }{ n }$ を求めよ．

10 進数 n を 3 進数に変換して 10 進数とみなす関数 ternary(n) をつくる．

例：100₁₀ = 10201₃ より， ternary(100) = 10201．

1 ≦ i < 3^d に対して ternary(i) を順に求めることで，d 桁以下かつ各桁の数字が 2 以下である数字を小さい順に列挙できる．

なんやかんや試すと 9999 を除けば f(n) は最大 16 桁であることがわかるので，
3¹⁶ = 43046721 個の配列に ternary(i) を格納して先頭から順に試し割りしていけばいい．

9999 はどうすんの？という話ですが

f(9) = 12222
f(99) = 1122222222
f(999) = 111222222222222

から類推して

f(9999) = 11112222222222222222

でいけるでしょう．N を下から n 桁ごとに区切って足したものが 10ⁿ - 1 の倍数なら N も 10ⁿ - 1 の倍数であることを利用すれば証明できそうですがだるいのでしません．

#include <iostream>
#include <time.h>

using namespace std;
typedef unsigned long long int lint;

lint ipow(lint x, lint n)
{
    lint i, ret = 1;
    for (i = 0; i < n; i++)
        ret *= x;
    return ret;
}

lint ternary(lint n)
{
    lint base = 1, rem, ret = 0;
    while (n != 0) {
        rem = n % 3;
        ret += base * rem;
        n /= 3;
        base *= 10;
    }
    return ret;
}

void PE0303() 
{
    const lint SIZE = ipow(3, 16);

    lint* sd = new lint[SIZE];

    for (lint i = 0; i < SIZE; i++)
        sd[i] = ternary(i);

    lint ans = 0;
    for (lint i = 1; i <= 10000; i++) {
        if (i == 9999)
            ans += (lint)11112222222222222222 / 9999;
        else {
            for (lint j = 1; j < SIZE; j++) {
                if (sd[j] % i == 0) {
                    ans += sd[j] / i;
                    break;
                }
            }
        }
    }
    cout << ans << endl;
}


int main()
{
    clock_t start, end;
    start = clock();

    PE0303();

    end = clock();
    printf("%d msec.\n", end - start);

    return 0;
}

20 秒くらい．

三進法って trinary じゃなくて ternary なんだね～

絶滅

どうでもいい

Project Euler - Problem 303

Multiples with small digits