P3996 A Failed Guessing Game

Daning is a person who likes gambling and has recently been playing a guessing game, but he keeps losing. He is very unhappy and goes to argue with the game operator, questioning whether the game's testdata is intentionally targeting players.

The game rules are as follows: The player gives three integers $A_0$, $a$, $b$, which define a linear recurrence: $A_i=a \times A_{i-1} +b$ It defines an infinite sequence { $A_1$, $A_2$, $A_3$, ... }. The game system randomly generates a number $n$. If $n$ can be represented as the sum of several distinct terms from this sequence (excluding $A_0$), the player wins; otherwise, the player loses. Now Daning has forced the operator to hand over a batch of recent game testdata, but he is too lazy to compute them one by one. Please help determine how many times the player won in the testdata.

The first line contains a positive integer $T$, the number of games played. Each of the next $T$ lines contains four integers, describing one game: $A_0$, $a$, $b$, $n$.

Output one line with $Ans$, the number of times the player won among the $T$ games.

Sample explanation: In games $1 \sim 3$ the player loses; in games $4 \sim 7$ the player wins. | Test point ID | Constraints | Special properties | | :----------: | :----------: | :----------: | | $1 \sim 2$ | $T=10$, $n \leq 10^3$ | $a=1$ | | $3 \sim 4$ | $T=10^3$, $n \leq 10^4$ | $a=2$ | | $5$ | $T=10^4$, $n \leq 10^9$ | $a \leq 3$ | | $6$ | $T=10^5$, $n \leq 10^9$ | $b=0$ | | $7 \sim 10$ | $T=2 \times 10^5$, $n \leq 10^9$ | None | For all testdata, $1 \leq a \leq 10$, $0 \leq b \leq 10^4$, $0 \leq n \leq 10^9$, $0 \leq A_0 \leq 100$. In fact, the player's win rate in this game is negligible. Translated by ChatGPT 5