G - Ai + Bj + Ck = X (1 <= i, j, k <= N) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

整数 N,A,B,C,X が与えられるので、以下の条件を全て満たす整数組 (i,j,k) の数を求めてください。

  • 1 \le i,j,k \le N
  • Ai+Bj+Ck=X

制約

  • 入力は全て整数
  • 1 \le N \le 10^6
  • 1 \le A,B,C \le 10^9
  • 1 \le X \le 3 \times 10^{15}

入力

入力は以下の形式で標準入力から与えられる。

N A B C X

出力

答えを整数として出力せよ。

入力例 1

5 3 1 5 15

出力例 1

3

条件を満たす整数組は以下の 3 つです。

  • (1,2,2) : 3 \times 1 + 1 \times 2 + 5 \times 2 = 15
  • (2,4,1) : 3 \times 2 + 1 \times 4 + 5 \times 1 = 15
  • (3,1,1) : 3 \times 3 + 1 \times 1 + 5 \times 1 = 15

入力例 2

1 1 1 1 1

出力例 2

0

入力例 3

100000 31415 92653 58979 1000000000

出力例 3

2896

Score : 550 points

Problem Statement

You are given integers N,A,B,C,X. Find the number of triples of integers (i,j,k) that satisfy all of the following conditions.

  • 1 \le i,j,k \le N
  • Ai+Bj+Ck=X

Constraints

  • All input values are integers.
  • 1 \le N \le 10^6
  • 1 \le A,B,C \le 10^9
  • 1 \le X \le 3 \times 10^{15}

Input

The input is given from Standard Input in the following format:

N A B C X

Output

Print the answer as an integer.

Sample Input 1

5 3 1 5 15

Sample Output 1

3

The following three triples satisfy the conditions.

  • (1,2,2) : 3 \times 1 + 1 \times 2 + 5 \times 2 = 15
  • (2,4,1) : 3 \times 2 + 1 \times 4 + 5 \times 1 = 15
  • (3,1,1) : 3 \times 3 + 1 \times 1 + 5 \times 1 = 15

Sample Input 2

1 1 1 1 1

Sample Output 2

0

Sample Input 3

100000 31415 92653 58979 1000000000

Sample Output 3

2896