[QkOI#R1] Quark and Equations 官方题解

· · 题解

建议在博客界面内查看

A - Quark and Equations

\text{Description}

给定 n,m，求下列方程组有几组正整数解，我们认为无解为 0 组解。

\begin{cases} i+j=n \\ \lfloor\frac{i}{j}\rfloor+\lceil\frac{j}{i}\rceil=m \end{cases}

本题单个数据点含多组数据。

1\le T\le 10^5,1\le n,m\le 10^{7} \text{Solution}

首先特判掉 n=1 的情况，显然无解。

显然当 m\in (-\infty,1]\cup[n+1,+\infty) 时无解，因为第二个方程的左边最大值和最小值分别为 n,2（实际上这是本来想出的）。

当 i<j 时，第二个方程实际上是 \lceil\frac{n}{i}\rceil=m+1。转换成不等式组：

\begin{cases}\begin{aligned}& i\le\lfloor\frac{n-1}{m}\rfloor \\& i\ge \lfloor\frac{n-1}{m+1}\rfloor+1 \end{aligned}\end{cases}

当 i\ge j 时，第二个方程实际上是 \lfloor\frac{n}{j}\rfloor=m。转换成不等式组：

\begin{cases}\begin{aligned}& j\le \lfloor\frac{n}{m}\rfloor \\& j\ge\lfloor\frac{n}{m+1}\rfloor+1 \end{aligned}\end{cases}

事实上已经把原先的小于/大于号通过奇怪的手段加上了等号，把没有取整符号的加上了取整符号，这样做起来会方便。

所以最后答案就是：

\lfloor\frac{n-1}{m}\rfloor-\lfloor\frac{n-1}{m+1}\rfloor+\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m+1}\rfloor