問題
http://yukicoder.me/problems/no/407
自然数 N, L が与えられる。
このとき、以下の条件を満たす数列の組合せを数えよ。
- 要素Nの数列 x0, x1, ... xN-1
- 0 <= x0 < x1 < x2 < ... < xN-1 <= L
- 隣り合う数の差が全て等しく、その差は素数である
3 <= N <= 10^6
1 <= L <= 10^7
考察
1. 素数問題は素数表をまず用意すると考えてるので「primes[i] = iが素数ならtrue,さもなければfalse」を作る
2. 何か1つ全列挙して数えられないか考える
3. 今回はある素数に対してO(1)で組合せが計算できるなら間に合う
4. ある素数dについて最初の要素を0とすると、
0, d, d*2, ..., d*(N-1)
横にずらすともう1通りでき、更に横にずらすともう1通りできる。
横にずらせるだけずらして、数える。
5. ずらせる回数は、L - d*(N-1) のため、ある素数dに対して、L - d*(N-1) + 1 通りのパターンがある
6. L < d*(N-1) となってしまうとダメなので、そうなったらbreak
実装
http://yukicoder.me/submissions/109382
vector<bool> primes; void make_primes(int n) { primes.resize(n + 1, true); primes[0] = primes[1] = false; rep(i, 2, sqrt(n)) { if (primes[i]) { for (int j = 0; i * (j + 2) < n; j++) primes[i * (j + 2)] = false; } } } //----------------------------------------------------------------- typedef long long ll; int N, L; //----------------------------------------------------------------- int main() { cin >> N >> L; make_primes(L); ll ans = 0; rep(i, 0, L) if(primes[i]) { int _max = i * (N - 1); if (L < _max) break; ans += L - _max + 1; } cout << ans << endl; }