等差数列计数｜求因数个数

题目链接：等差数列计数

题目描述

首先根据题目要求，给定一个等差数列的首项 $t_1$ 和这个等差数列的末项 $t_n$，问符合这个形式的等差数列的数量。

例如，对于第一个 $\mathtt{Testcase}$，当 $t_1$ 为 $1$，$t_n$ 为 $9$ 时，可行的等差数列方案数有四个，分别为以下所示：

1. $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$
2. $S = \{1, 3, 5, 7, 9\}$
3. $S = \{1, 5, 9\}$
4. $S = \{1, 9\}$

思路分析

我们知道，等差数列的公差数量就是这个等差数列的可行方案数，即有多少种不同的公差方案，就可以构造出多少种不同的等差数列。因此通过分析题意，我们可以将问题更细致地转换为 已知等差数列的首项和尾项，求出这个等差数列公差的可行方案数。所以对于本题而言，我们只需要求出有多少个公差就可以了。

显然本题的就引刃而解了，我们只需要求出这个等差数列首项和末项的差的绝对值，即 $diff = \lvert t_n - t_1 \rvert$。然后我们只需要求出 $diff$ 的因数个数即可。$diff$ 的因数就是可行的因数方案（详细证明过程见下文）。

例如，当 $t_1$ 为 $1$，$t_n$ 为 $9$ 时，$diff = \lvert 9 - 1 \rvert = 8$。$8$ 的因数有四个，分别是 $\{1, 2, 4, 8\}$，因此当这个等差数列首项为 $1$，末项为 $9$ 时，可行的等差数列方案应为四个。

结论证明

通过等差数列公式，我们可以将等差数列的首项和末项通过公式联立起来，得到 $t_n = t_1 + (n-1)\times d$，其中 $n$ 表示等差数列的项数，$d$ 表示等差数列的公差。

由于我们想要求解所有的因数个数，因此我们将通过移项的操作将 $d$ 放到等式左边，将其余的量都放到等式右边。得到：

$$\begin{equation} \begin{split} t_n - t_1 &= (n-1) \times d \\ d &= \frac{t_n - t_1}{n-1} \end{split} \end{equation}$$

由于等差数列的性质，$n - 1$ 必须为非负整数（等差数列的长度不能 $0$）。或者根据等差数列的另一个性质，如果首项和末项的差为负数，那么公差也必须为负数，反之亦然。因此也可以推导出 $n - 1$ 必须是非负整数。

为了方便起见，我们将 $n-1$ 看作为一个整体，另 $\Delta t = n - 1$。将该整体代入方程后即可得到 $d = \frac{t_n - t_1}{\Delta t}$。为了使 $d$ 是一个整数，因此 $t_n - t_1$ 必须是 $\Delta t$ 的倍数。因此我们只需要通过枚举上述方程，计算 $t_n - t_1$ 所有的因数数量就可以得到本问题的解。

AC 代码

以下是本题的 AC 代码。需要注意的是，由于本题的数据量比较大，因此在判断因数的过程中需要优化算法（与判断质数类似），这样子算法就可以在 $O(\sqrt{n})$ 的时间内完成枚举，不至于超时：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int t, a, b;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> a >> b;
        int change = abs(b - a), cnt = 0;
        for (int i=1; i*i<=change; i++){
            if (change % i == 0){
                if (i*i != change) cnt += 2;
                else cnt += 1;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}