题解：[QkOI#R1] Quark and Equations

这道题给定 $n,m$，要求方程组的解的数量。若无解，则输出 $0$。

$\texttt{Subtask 1}$

直接两层循环，从 $1$ 至 $\max(n,m)$ 枚举 $i,j$，若满足条件，则将答案 $+1$。

$\texttt{Subtask 2}$

由方程组的 $i + j = n$ 可知 $i = n - j$，也就是说对于一个 $i$ 都会有一个对应的 $j$，因此可以化简为一层循环。

$\texttt{Subtask 3-5}$

当 $m = 1$时，$\lfloor \dfrac{i}{j} \rfloor + \lceil \dfrac{j}{i} \rceil = 1$。由题知，$i > 0,j > 0$，则 $\lfloor\dfrac{i}{j}\rfloor =0,\lceil\dfrac{j}{i}\rceil =1$，即 $j > i$ 且 $j \le i$,显然此时无解。

而当 $m > n$ 或 $m \in[n - 1,n]$ 时，同理能证得无解。

$\texttt{subtask 6}$

最后来看正解，对 $i,j$进行分类讨论。

• $i < j$，$\lfloor \dfrac{i}{j} \rfloor = 0$，即 $\lceil \dfrac{j}{i} \rceil = m$。

• $i \ge j$，$\lceil \dfrac{j}{i} \rceil= 1$，即 $\lfloor \dfrac{i}{j} \rfloor = m + 1$。

联立两式，于是我们就能得到两个不等式，整理可得最终答案为：
$\lceil \dfrac{n - 1}{m} \rceil - \lceil \dfrac{n - 1}{m + 1} \rceil + \lceil \dfrac{n}{m} \rceil - \lceil \dfrac{n}{m + 1} \rceil$。

代码：
注意特判哦！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long ans = 0,n,m;scanf("%lld%lld",&n,&m);
        if(m == 1)
        {
            cout<<0<<endl;
            continue;
        }
        ans = floor((n - 1) / m) - floor((n - 1) / (m + 1)) + floor(n / m) - floor(n / (m + 1));
        printf("%lld\n",ans);
    } 
    return 0;
}