P3090 [USACO13NOV] Empty Stalls G

Farmer John's new barn consists of a huge circle of $N$ stalls ($2 \le N \le 3{,}000{,}000$), numbered $0..N-1$, with stall $N-1$ being adjacent to stall $0$. At the end of each day, FJ's cows arrive back at the barn one by one, each with a preferred stall they would like to occupy. However, if a cow's preferred stall is already occupied by another cow, she scans forward sequentially from this stall until she finds the first unoccupied stall, which she then claims. If she scans past stall $N-1$, she continues scanning from stall $0$. Given the preferred stall of each cow, determine the smallest index of a stall that remains unoccupied after all the cows have returned to the barn. Notice that the answer does not depend on the order in which the cows return. To avoid reading huge amounts of input, the input is specified concisely using $K$ lines ($1 \le K \le 10{,}000$), each of the form: X Y A B One such line specifies preferences for $X \times Y$ cows in total: $X$ cows prefer each of the stalls $f(1), \dots, f(Y)$, where $f(i) = (A i + B) \bmod N$. The values of $A$ and $B$ lie in the range $0 \dots 1{,}000{,}000{,}000$. Note: The standard memory limit is 64 MB.

约翰的谷仓中有 $N(2 \le N \le 3\times 10^{6})$ 个房间，编号 $0$ 到 $N-1$，这些房间排布成环状,编号 $0$ 的和编号 $N-1$ 的相邻。 每天傍晚，奶牛们一只一只排队回到谷仓，每头奶牛都有一个喜欢的房间，但是，如果它喜欢的房间已被其他奶牛占了，它会向前挨个探索其他房间（如果它探索过了 $N-1$ 号房间，它会继续探索 $0$ 号房间，以此继续下去）直到探到第一个没有被占用的房间，这时它会宣布占用这个房间。 告诉你每头奶牛喜欢的房间，当所有奶牛都找到房间后，剩下的没被占用的房间中，编号最小的是哪个。很明显，问题的答案与奶牛进入谷仓的顺序无关。 为避免输入内容过多。本题的输入数据采用一种简洁的方式：一共 $K(1 \le K \le 10^{4})$ 行，每行格式如下： > $X\ Y\ A\ B$ 表示有 $Y$ 批奶牛，每批 $X$ 头，也就是总共 $X\times Y$ 只奶牛喜欢的房间号。$Y$ 批奶牛编号 $1$ 到 $Y$，第 $i$ 批 $X$ 头奶牛喜欢的房间号为$(A \times i+B) \bmod N$。 $A$ 和 $B$ 的取值范围为 $0\dots 10^{9}$。 注意，只有 64M 的空间。

第一行，两个用空格隔开的整数,$N$ 和 $K$。 第二行到第 $K+1$ 行，每行包含四个整数 $X,Y,A,B$，解释看题目描述。牛的总数最多为 $N-1$ ，可以向同一个牛栏中添加牛。

一行一个整数，表示最小的移动次数。

谷仓里有 $10$ 个牛栏，编号为 $0$ 到 $9$。输入的第二行表示有 $3$ 头牛喜欢牛栏 $(2 \times 1 + 4) \bmod 10 = 6$，另有 $3$ 头牛喜欢牛栏 $(2 \times 2 + 4) \bmod 10 = 8$。第三行表示有 $2$ 头牛喜欢牛栏 $(0\times 1 + 1) \bmod 10 = 1$。第四行表示有 $1$ 头牛喜欢牛栏 $(1 \times 1 + 7) \bmod 10 = 8$（所以总共有 $4$ 头牛喜欢这个牛栏）。 除了牛栏 $5$ 之外，其他所有牛栏最后都会被占用。