Project Euler - Problem 581
47-smooth triangular numbers
p より大きい素因数を含まない数は p-smooth であるという.
T を三角数の列とする.すなわち T(n) = n(n+1)/2.
T(n) が 47-smooth となるような全てのインデックス n の総和を求めよ.
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 になる.
108 くらいまでは出るけどもっとでかい数が無数にあり,無理
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 = 241 近くまであるしそりゃ 64bit でもだめだわ.
2.9 sec くらい