問題一覧 > 通常問題

No.2280 FizzBuzz Difference

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 49
作問者 : miscalc / テスター : magsta
お気に入りにしたユーザー ProblemId : 8702 / 自分の提出
問題文最終更新日: 2023-06-06 05:21:01
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 385 (順位表) の他の問題:

Problem Statement

Suppose there are $N$ positive integers not exceeding $M$ that are multiples of $A$ or multiples of $B$, and consider the sequence $X = (X_1, X_2, \ldots, X_N)$ formed by arranging all of them in ascending order.

How many integers $i$ ($1 \leq i \leq N - 1$) satisfy $X_{i+1} - X_i = K$?

You are given $T$ test cases; find the answer for each of them.

Input

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format.

$M$ $A$ $B$ $K$

  • All input values are integers.
  • $1 \leq T \leq 10^4$
  • $1 \leq A < B \leq 10^9$
  • $A \leq M \leq 10^{18}$
  • $1 \leq K \leq 10^9$

Output

For each test case, output the answer. Print a newline after each test case.

Sample

Sample 1
Input
8
18 3 5 1
18 3 5 2
18 3 5 3
18 3 5 4
150 4 7 3
1000 10 20 10
1000000000000000000 999999999 1000000000 314159265
1000000000000000000 2 3 1
Output
2
2
3
0
11
99
2
333333333333333334

For the $1, 2, 3, 4$-th test cases, $X = (3, 5, 6, 9, 10, 12, 15, 18)$, and the difference sequence of $X$ (the sequence of $X_{i+1} - X_i$) is $(2, 1, 3, 1, 2, 3, 3)$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。