No.407 鴨等素数間隔列の数え上げ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 111
作問者 : はむ吉🐹はむ吉🐹 / テスター : btkbtk

0 ProblemId : 1232 / 出題時の順位表

問題文

太郎君は今日も近くの河川敷にやってきました。
ほどなくして、$N\:(\ge 3)$羽の鴨の一団が休みにやってきました。
彼らはやや変わり者で、自分たちが休む場所を次の規則で決めるようです。
この川は十分に長く、まっすぐに流れているので、河川敷上にこれと平行になるように$x$軸をとり、適当に原点$x=0$を定めます。
そして、鴨$i\:(0\le i \lt N)$が休む場所を、この$x$軸上にあって、座標が$x_i$である点とします。
さらに、座標の列$\{x_i\}_{i = 0, 1, \cdots, N - 1}$、すなわち$(x_0, x_1, \cdots, x_{N - 1})$は次の条件を満たすものとします。
ただし、$L$は$N$羽の鴨全員が気に入っている一つの正整数とします。

  1. $x_0, x_1, \cdots, x_{N - 1}$はすべて非負整数である。
  2. $0 \le x_0 \lt x_1 \lt x_2 \lt\cdots \lt x_{N - 1} \le L$である。
  3. $x_1 - x_0 = x_2 - x_1 = \cdots = x_{N - 1} - x_{N - 2} = d$($d$は素数)である。

座標の列$\{x_i\}_{i = 0, 1, \cdots, N - 1}$が以上を満たすときに限り、$\{x_i\}_{i = 0, 1, \cdots, N - 1}$が鴨等素数間隔列であるということにします。
鴨の一団に頼まれて、太郎君は鴨等素数間隔列である$\{x_i\}_{i = 0, 1, \cdots, N - 1}$の数$M_{N, L}$を計算しようとしましたが、うまくできませんでした。
$N$と$L$が与えられるので、彼らの代わりに$M_{N, L}$を計算してください。

入力

$N$ $L$

1行目に、正の整数$N\:(3 \le N \le 10 ^ 6)$および$L\:(1 \le L\le 10 ^ 7)$がスペース区切りで与えられます。

出力

非負整数$M_{N, L}$を1行で出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 5
出力
2

この場合に、鴨等素数間隔列である$\{x_i\}_{i = 0, 1, 2}$は、(0, 2, 4)と(1, 3, 5)に限られます。

サンプル2
入力
5 12
出力
6

鴨等素数間隔列である$\{x_i\}_{i = 0, 1, 2, 3, 4}$は次の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)
サンプル3
入力
3 1
出力
0

鴨等素数間隔列がひとつもないことがあります。

サンプル4
入力
8 964853
出力
6502770112

サンプル5
入力
57 56
出力
0

提出ページヘ