Project Euler - Problem 581

47-smooth triangular numbers

Problem 581

p より大きい素因数を含まない数は p-smooth であるという．
T を三角数の列とする．すなわち T(n) = n(n+1)/2．
T(n) が 47-smooth となるような全てのインデックス n の総和を求めよ．

• T(n) が 47-smooth であるかどうか n = 1 から順番に調べる

普通に無理　ただ 5-smooth とかで調べると有限であるらしいことはわかる．

• エラトステネスの篩的な方法で i の最大素因数を dp[i] に格納し，
  max(dp[i], dp[i+1]) <= 47 であるものを探す．

T(n) = n (n + 1) / 2 なので，n と n + 1 が 47-smooth であれば T(n) も 47-smooth になる．
10⁸ くらいまでは出るけどもっとでかい数が無数にあり，無理

• 再帰で 47-smooth である数を生成し，三角数であるものを拾ってくる

64bit int でもカウントし切れていない気がする．時間めっちゃかかる．答え合わない．

• 再帰で 47-smooth である数 n を生成し，n + 1 が 47-smooth であるものを拾ってくる

dp 書いたんだからこの方法が二秒で浮かんでいいはずなのに， 3 日くらいわかんなくて放置してた．アホか

typedef long long ll;

#define MAX (1LL << 41)
const ll p[15] = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 };

bool is_smooth47(ll x) {
    for (int i = 0; i < 15; i++) {
        while (x % p[i] == 0) x /= p[i];
    }
    return (x == 1 ? true : false);
}

ll ans;

// 47-smooth number を列挙する再帰関数
void rec(ll x = 1, uint pos = 0) {
    if (pos == 15) {
        if (is_smooth47(x + 1)) ans += x;
        return;
    }
    // p[pos] を何回かかける
    for (; x <= MAX; x *= p[pos]) {
        rec(x, pos + 1);
    }
}

int main() {

    clock_t start, end;
    start = clock();

    rec();
    cout << ans << endl;

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

    return 0;
}

n = 2⁴¹ 近くまであるしそりゃ 64bit でもだめだわ．

2.9 sec くらい