CF1292B.Aroma's Search

THE SxPLAY & KIVΛ - 漂流

KIVΛ & Nikki Simmons - Perspectives

With a new body, our idol Aroma White (or should we call her Kaori Minamiya?) begins to uncover her lost past through the OS space.

The space can be considered a 2D plane, with an infinite number of data nodes, indexed from $0$, with their coordinates defined as follows:

• The coordinates of the $0$-th node is $(x_0, y_0)$
• For $i \gt 0$, the coordinates of $i$-th node is $(a_x \cdot x_{i-1} + b_x, a_y \cdot y_{i-1} + b_y)$

Initially Aroma stands at the point $(x_s, y_s)$. She can stay in OS space for at most $t$ seconds, because after this time she has to warp back to the real world. She doesn't need to return to the entry point $(x_s, y_s)$ to warp home.

While within the OS space, Aroma can do the following actions:

• From the point $(x, y)$, Aroma can move to one of the following points: $(x-1, y)$, $(x+1, y)$, $(x, y-1)$ or $(x, y+1)$. This action requires $1$ second.
• If there is a data node at where Aroma is staying, she can collect it. We can assume this action costs $0$ seconds. Of course, each data node can be collected at most once.

Aroma wants to collect as many data as possible before warping back. Can you help her in calculating the maximum number of data nodes she could collect within $t$ seconds?

THE SxPLAY & KIVΛ - 漂流

KIVΛ & Nikki Simmons - Perspectives

获得新身体后，我们的偶像 Aroma White（抑或该称她为 Kaori Minamiya？）开始在操作系统空间（OS space）中探寻自己失落的过往。

该空间可视为一个二维平面，其中分布着无限多个数据节点，节点编号从 $0$ 开始，其坐标定义如下：

• 第 $0$ 号节点的坐标为 $(x_0, y_0)$；
• 对于 $i > 0$，第 $i$ 号节点的坐标为 $(a_x \cdot x_{i-1} + b_x,\; a_y \cdot y_{i-1} + b_y)$。

初始时，Aroma 位于点 $(x_s, y_s)$。她在 OS 空间中最多可停留 $t$ 秒，因为超过该时限后她必须返回现实世界。她无需回到入口点 $(x_s, y_s)$ 即可完成传送。

在 OS 空间内，Aroma 可执行以下操作：

• 从点 $(x, y)$ 出发，Aroma 可移动至以下四个点之一：$(x-1, y)$、$(x+1, y)$、$(x, y-1)$ 或 $(x, y+1)$。每次移动耗时 $1$ 秒；
• 若 Aroma 当前所处位置恰好存在一个数据节点，则她可收集该节点。我们假定此操作耗时为 $0$ 秒。当然，每个数据节点至多只能被收集一次。

Aroma 希望在返回前尽可能多地收集数据节点。你能帮她计算出：在 $t$ 秒内最多可收集多少个数据节点吗？

The first line contains integers $x_0$, $y_0$, $a_x$, $a_y$, $b_x$, $b_y$ ($1 \leq x_0, y_0 \leq 10^{16}$, $2 \leq a_x, a_y \leq 100$, $0 \leq b_x, b_y \leq 10^{16}$), which define the coordinates of the data nodes.

The second line contains integers $x_s$, $y_s$, $t$ ($1 \leq x_s, y_s, t \leq 10^{16}$) – the initial Aroma's coordinates and the amount of time available.

第一行包含整数 $x_0$、$y_0$、$a_x$、$a_y$、$b_x$、$b_y$（满足 $1 \leq x_0, y_0 \leq 10^{16}$，$2 \leq a_x, a_y \leq 100$，$0 \leq b_x, b_y \leq 10^{16}$），用于定义数据节点的坐标。

第二行包含整数 $x_s$、$y_s$、$t$（满足 $1 \leq x_s, y_s, t \leq 10^{16}$）——即 Aroma 的初始坐标以及可用的时间总量。

Print a single integer — the maximum number of data nodes Aroma can collect within $t$ seconds.

输出一个整数——Aroma 在 $t$ 秒内最多能收集的数据节点数量。

In all three examples, the coordinates of the first $5$ data nodes are $(1, 1)$, $(3, 3)$, $(7, 9)$, $(15, 27)$ and $(31, 81)$ (remember that nodes are numbered from $0$).

In the first example, the optimal route to collect $3$ nodes is as follows:

• Go to the coordinates $(3, 3)$ and collect the $1$-st node. This takes $|3 - 2| + |3 - 4| = 2$ seconds.
• Go to the coordinates $(1, 1)$ and collect the $0$-th node. This takes $|1 - 3| + |1 - 3| = 4$ seconds.
• Go to the coordinates $(7, 9)$ and collect the $2$-nd node. This takes $|7 - 1| + |9 - 1| = 14$ seconds.

In the second example, the optimal route to collect $2$ nodes is as follows:

• Collect the $3$-rd node. This requires no seconds.
• Go to the coordinates $(7, 9)$ and collect the $2$-th node. This takes $|15 - 7| + |27 - 9| = 26$ seconds.

In the third example, Aroma can't collect any nodes. She should have taken proper rest instead of rushing into the OS space like that.

在全部三个示例中，前 $5$ 个数据节点的坐标依次为 $(1, 1)$、$(3, 3)$、$(7, 9)$、$(15, 27)$ 和 $(31, 81)$（注意：节点编号从 $0$ 开始）。

在第一个示例中，收集 $3$ 个节点的最优路径如下：

• 前往坐标 $(3, 3)$ 并收集第 $1$ 个节点。耗时 $|3 - 2| + |3 - 4| = 2$ 秒。
• 前往坐标 $(1, 1)$ 并收集第 $0$ 个节点。耗时 $|1 - 3| + |1 - 3| = 4$ 秒。
• 前往坐标 $(7, 9)$ 并收集第 $2$ 个节点。耗时 $|7 - 1| + |9 - 1| = 14$ 秒。

在第二个示例中，收集 $2$ 个节点的最优路径如下：

• 收集第 $3$ 个节点。耗时 $0$ 秒。
• 前往坐标 $(7, 9)$ 并收集第 $2$ 个节点。耗时 $|15 - 7| + |27 - 9| = 26$ 秒。

在第三个示例中，Aroma 无法收集任何节点。她本应好好休息，而不该如此仓促地闯入操作系统空间。