問題一覧 > 通常問題

No.407 Counting Duck Equal-Prime-Interval Sequences

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 223
作問者 : はむ吉🐹 / テスター : btk
お気に入りにしたユーザー ProblemId : 1232 / 自分の提出
問題文最終更新日: 2026-06-25 04:46:12
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 145 (順位表) の他の問題:

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.

  1. $x_0, x_1, \cdots, x_{N - 1}$ are all non-negative integers.
  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$ 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もしくは右上の雲マークをクリックしてアカウントを作成してください。