デンソークリエイトプログラミングコンテスト2026（AtCoder Beginner Contest 443）
翻译中…
Problem Statement
翻译中…
You are given integers $N,M,A,B$.
翻译中…
Define an integer sequence $X=(X_0,X_1,\ldots,X_{N-1})$ as $\displaystyle X_k = (Ak+B) \bmod M$.
翻译中…
Find the number of integers $k$ satisfying $0 \le k < N$ and $X_k > k$.
翻译中…
You are given $T$ test cases; solve each of them.
翻译中…
Constraints
翻译中…
$1\le T\le 3\times 10^5$$1\le N \le M\le 10^9$$0\le A,B < M$- All input values are integers.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T翻译中…
Each test case is given in the following format:
翻译中…
N M A B翻译中…
Output
翻译中…
Output the answers for the test cases in order, separated by newlines.
翻译中…
样例
Input #1
4
4 6 4 3
7 7 3 1
10 46 0 12
443 2026 131 210
Output #1
2
3
10
395
Consider the first test case.
- When $k=0$: $X_0=(4\times 0+3)\bmod 6=3$, so $X_k>k$ holds.
- When $k=1$: $X_1=(4\times 1+3)\bmod 6=1$, so $X_k>k$ does not hold.
- When $k=2$: $X_2=(4\times 2+3)\bmod 6=5$, so $X_k>k$ holds.
- When $k=3$: $X_3=(4\times 3+3)\bmod 6=3$, so $X_k>k$ does not hold.
From the above, the integers $k$ satisfying $0 \le k < 4$ and $X_k>k$ are $k=0,2$, which is two integers. Thus, output $2$ on the first line.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。