P9007 题解
首先大力推式子。
为了方便，先假设 \(2 \leq z\)。
\(x - \frac{y}{z} = n\)
\(\frac{x-y}{z} = (n-1) !\)
很显然的 \(z | x\) 以及 \(z | y\)
令 \(m= \frac{x}{z}\) 以及 \(k = \frac{y}{z}\)
得到 \(\frac{m \times z - k}{m - k}=n\)
\((m \times z - k) = n \times (m - k)\)
\((m - k) + (z - 1) \times m = n \times (m - k)\)
\((z - 1) \times m = (n - 1) \times (m - k)\)
\((z - 1) | (n - 1) \times (m - k)\)
\((z - 1) | (n - 1) \times (m - k) \times z\)
\((z - 1) | (n - 1) \times (x - y)\)
\((z - 1) | (n - 1) \times (n - 1) ! \times z\)
因为 \(\gcd(z,z - 1)=1\)
所以有
$(z - 1) | (n - 1) \times (n - 1) ! $
然后注意到确定了 \(n,z\) 后，两个一次方程可以确定一个唯一的一组解。
所以答案就成了 \((n - 1) \times (n - 1) !\) 的因数个数。
但是我们可以预处理。
首先标记需要输出答案的 \(n\)。
首先我们可以用线性筛筛出每个数每种质因子的幂次。
具体来说，首先在线性筛时存储每个数被那哪些数筛掉了，这些数就是它的质因子做除法得出。接着对于每个数对每个质因子做除法得出幂次。
那么令 \(f_i = (i - 1) \times (i - 1) !\)。
有 \(f_i = \frac{f_{i - 1} \times i^2}{i - 1}\)
所以每次 \(i\) 的质因子幂次加上 \(i\) 中幂次的两倍，\(i - 1\) 的质因子幂次减去 \(i - 1\) 中幂次的一倍，如果这个 \(i\) 被询问，那么用所有质因子幂次加 \(1\) 之积计算因数数量。
但是由于幂次过多，这样会 TLE 。
所以只维护答案，每次修改就暴力把每个质因子的贡献修改。
显然这样是要求逆元的，这里需要预处理。
考虑对于 \((n - 1) !\) 某个质因子的幂次 \(\leq \sum_{i = 1}^{k} \frac{n}{2^i} \leq n\)。
所以只要处理 \(1 \to n\) 的逆元即可。
那么总复杂度就是 \(O(n \log n + T)\) 的。
那如果 \(z = 1\) 呢？
带入前面的式子，有 \(n = (n - 1) !\) ，即 \(n = 1\)。
此时显然任意 \(x - y = 1\) 都可以满足条件，故输出 inf 即可。