B
时间:看了题解后花了 \(30\) 多分钟吧。
给定 \(n\) 对数 \((a_i, b_i)\) 以及 \(T\) 组询问,每组询问给定 \((x, y)\),问有多少对给定的数能通过对 \((x, y)\) 进行若干次以下两种操作得到?
- \((x, y) \leftarrow (x, x + y)\)。
- \((x, y) \leftarrow (x + y, y)\)。
\(n, T \le 10^5, 1 \le a_i, b_i, x, y \le 10^{18}\)。
正着做似乎毫无前途,至少我考时打了一个小时表毫无规律,它进行不同的操作后也几乎不会到达重复的状态,然后就寄了。
看了一眼题解,告诉我们要倒着做,然后几乎就秒会了。
首先操作肯定是可逆的,无非是 \((x, y) \leftarrow (x - y, y)\) 和 \((x, y) \leftarrow (x, y - x)\)。但是倒着做有什么好处呢?
凭借我们惊人的注意力:\(a_i, b_i, x, y\) 都是大于 \(0\) 的,而一个带有负数的对 \((-p, q)\) 无论怎么操作都至少还有一个负数,所以减的时候一定时大的减小的,操作时唯一确定的,而不是有两种。
而这玩意很像辗转相除法,只不过是减法。但是一个个减肯定会超时,还是只能按照辗转相除法做。
不妨设 \(a_i > b_i, k = a_i \% b_i\),则 \((k, b_i), (k + y, b_i) , \dots , (a_i, b_i)\) 都是可以的。我们可以把这些数概括成一个三元组 \((b_i, k, a_i)\) 表示对于询问的 \((x, y)\),若 \(y = b_i, x \% y = k, x \le a_i\) \((x, y)\) 就是那一串数中的一个。
那么将所有 \(n \log V\) 个三元组排序,然后查询时二分出一段区间即可得到答案。对于 \(a_i < b_i\) 的情况同样的做一遍即可,两边互不影响。
时间复杂度:\(O(n \log V \log n)\),注意下常数还是能过的。
似乎 \((k, b_i)\) 到辗转相除一次时会再算一次,不过将 \(y \le b_i\) 改成 \(y \le b_i - x\) 就可以了。
这个题难点就是要想到倒着做,这样操作时固定的,然后就不难了。(脑瘫了,一直想正着做。)