No.407 Counting Duck Equal-Prime-Interval Sequences
Problem Statement
Today, Taro came to the nearby riverbank again.
Before long, a group of $N\:(\ge 3)$ ducks came to rest.
They are somewhat eccentric, and they seem to decide where to rest according to the following rule.
This river is sufficiently long and flows straight, so we take an $x$-axis on the riverbank parallel to the river and choose an origin $x=0$ appropriately.
Then, the place where duck $i\:(0\le i \lt N)$ rests is the point on this $x$-axis with coordinate $x_i$.
Furthermore, the sequence of coordinates $\{x_i\}_{i = 0, 1, \cdots, N - 1}$, that is, $(x_0, x_1, \cdots, x_{N - 1})$, must satisfy the following conditions.
Here, $L$ is a positive integer that all $N$ ducks like.
- $x_0, x_1, \cdots, x_{N - 1}$ are all non-negative integers.
- $0 \le x_0 \lt x_1 \lt x_2 \lt\cdots \lt x_{N - 1} \le L$.
- $x_1 - x_0 = x_2 - x_1 = \cdots = x_{N - 1} - x_{N - 2} = d$ ($d$ is a prime number).
Only when the sequence of coordinates $\{x_i\}_{i = 0, 1, \cdots, N - 1}$ satisfies the above do we say that $\{x_i\}_{i = 0, 1, \cdots, N - 1}$ is a duck equal-prime-interval sequence.
At the request of the group of ducks, Taro tried to compute the number $M_{N, L}$ of $\{x_i\}_{i = 0, 1, \cdots, N - 1}$ that are duck equal-prime-interval sequences, but he could not do it successfully.
Given $N$ and $L$, compute $M_{N, L}$ on their behalf.
Input
$N$ $L$
The first line contains positive integers $N\:(3 \le N \le 10 ^ 6)$ and $L\:(1 \le L\le 10 ^ 7)$, separated by a space.
Output
Print the non-negative integer $M_{N, L}$ on one line. Print a newline at the end.
Sample
Sample 1
Input
3 5
Output
2
In this case, the only duck equal-prime-interval sequences $\{x_i\}_{i = 0, 1, 2}$ are (0, 2, 4) and (1, 3, 5).
Sample 2
Input
5 12
Output
6
The duck equal-prime-interval sequences $\{x_i\}_{i = 0, 1, 2, 3, 4}$ are only the following 6.
- (0, 2, 4, 6, 8)
- (0, 3, 6, 9, 12)
- (1, 3, 5, 7, 9)
- (2, 4, 6, 8, 10)
- (3, 5, 7, 9, 11)
- (4, 6, 8, 10, 12)
Sample 3
Input
3 1
Output
0
There may be no duck equal-prime-interval sequences at all.
Sample 4
Input
8 964853
Output
6502770112
Sample 5
Input
57 56
Output
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
はむ吉🐹
btk