Project Euler - Problem 601
Divisibility streaks
正の数 n に対して, n+k が k+1 で割り切れないような最小の正の整数kをもって関数 streak(n)=k と定義しよう.
例えば:
13は1で割り切れる
14は2で割り切れる
15は3で割り切れる
16は4で割り切れる
17は5で割り切れない
よって, streak(13)=4
同様に:
120は1で割り切れる
121は2で割り切れない
よって, streak(120)=1
1 < n < N を満たし streak(n)=s である整数 n の個数を P(s,N) と定義する.
例えば, P(3,14)=1, P(6,106)=14286 となる.
i が 1 から 31 の範囲にあるときの P(i, 4i) の和を求めよ.
(日本語訳より)
例えば:
13は1で割り切れる
14は2で割り切れる
15は3で割り切れる
16は4で割り切れる
17は5で割り切れない
よって, streak(13)=4
同様に:
120は1で割り切れる
121は2で割り切れない
よって, streak(120)=1
1 < n < N を満たし streak(n)=s である整数 n の個数を P(s,N) と定義する.
例えば, P(3,14)=1, P(6,106)=14286 となる.
i が 1 から 31 の範囲にあるときの P(i, 4i) の和を求めよ.
(日本語訳より)
簡単な実験により
streak(n) ≧ s ⇔ n = k * LCM(1, 2, ..., s) + 1 (k = 1, 2, ...)
がわかる.証明はだるいのでしません.
P(i, 4i) を求める際のループ回数は約 4i / LCM(1, ..., i) 回ですが,これは最大でも i = 28 の時の約 900,000 回で済むのですぐに答えがでる.
typedef long long lint lint LCM(lint m, lint n) { lint k; lint m_tmp = m, n_tmp = n; do { k = m % n; m = n; n = k; } while (k != 0); return m_tmp / m * n_tmp; } lint streak(lint n) { for (lint k = 0; ; k++) { if ((n + k) % (k + 1) != 0) return k; } } lint P(lint s, lint N) { lint lcm = 1; for (lint i = 2; i <= s; i++) lcm = LCM(lcm, i); lint ret = 0; for (lint n = lcm + 1; n < N; n += lcm) { if (streak(n) == s) ret++; } return ret; } int main() { clock_t start, end; start = clock(); lint ans = 0; for (lint i = 1; i <= 31; i++) ans += P(i, 1LL << (2 * i)); cout << ans << endl; end = clock(); printf("%f sec.\n", double(end - start) / CLOCKS_PER_SEC); return 0; }
0.7 sec くらい.