はまやんはまやんはまやん

hamayanhamayan's blog

鴨等素数間隔列の数え上げ [yukicoder 407]

問題

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;
}