未命名

lk的梦想

众所周知，任何一个数我们都可以写成一些质数和 1 的乘积。 比如说 12 可以写作 $1\times 3\times 2\times 2$ 也就是 $1\times 3\times 2^2$ ，由此我们可以很容易的求出他的约数的个数。 12 的约数个数就可以由他的质因子和 1 组合而来：$1\times (2+1)\times (1+1)=6$。 算出来 L 到 R 区间所有数的平方的约数个数之和。 输入两个数 L, R(1 ≤ L ≤ R ≤ 107)。 输出一个数，表示约数的个数。

分析

如果一个数的平方的约数个数要求，我们可以考虑先求出这个数的约数个数，再求出这个数的平方，最后再求出这个数的平方的约数个数。

例如，如果我们想求出$24$的平方的约数个数，首先我们求出$24$的约数个数，可以得到$24$有$8$个约数，即$1,2,3,4,6,8,12,24$。求出$24$的平方，即$24^2=576$。最后，我们求出$576$的约数个数，可以得到$576$有$16$个约数， 即$1,2,3,4,6,8,9,12,16,18,24,36,48,72,144,576$。因此，$24$的平方的约数个数是$16$。

对于一个给定的数$n$，我们可以通过以下步骤来求出它的平方的约数个数：

1. 求出$n$的约数个数$cn{t}_n$；
2. 求出$n^2$的约数个数$cn{t}_{n^2}$；
3. 返回$cn{t}_{n^2}$。

下面我们来给出这个算法的一个实现。

首先，我们需要一个函数$cnt(n)$来求出$n$的约数个数。我们可以使用如下的代码来实现这个函数：

int cnt(int n) {
    int res = 0;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            res += 2;
            if (i * i == n) --res;
        }
    }
    return res;
}

接下来，我们可以定义一个函数$solve(L,R)$来求出$L$到$R$区间所有数的平方的约数个数之和。我们可以使用如下的代码来实现这个函数：

int solve(int L, int R) {
    int res = 0;
    for (int i = L; i <= R; ++i) {
        res += cnt(i * i);
    }
    return res;
}

最后，我们可以在主函数中调用$solve(L,R)$函数，并输出它的结果。

为了降低时间复杂度，我们可以将$solve$函数中的循环改为类似于$cnt$函数中的方式来实现，即：

int solve(int L, int R) {
    int res = 0;
    for (int i = 1; i * i <= R; ++i) {
        int j = max(i * i, L);
        if (j <= R) res += (R - j) / i + 1;
    }
    return res;
}

这样，时间复杂度就降低到了$O(\sqrt{R})$。

另外，我们还可以通过求出每个数的平方的约数个数，然后再统计区间和来实现这个算法。这样可以将时间复杂度进一步降低到$O(R)$。

具体的，我们可以使用如下的代码来实现这个算法：

const int N = 1e7 + 5;
int cnt[N];
 
void init() {
    for (int i = 1; i < N; ++i) {
        for (int j = i; j < N; j += i) {
            cnt[j]++;
        }
    }
    for (int i = 1; i < N; ++i) {
        cnt[i] += cnt[i - 1];
    }
}
 
int solve(int L, int R) {
    return cnt[R] - cnt[L - 1];
}
 

在主函数中，我们需要先调用$init$函数来求出每个数的平方的约数个数，然后再调用$solve$函数并输出结果即可。

完整代码

const int N = 1e7 + 5;
int cnt[N];
 
void init() {
    for (int i = 1; i < N; ++i) {
        for (int j = i; j < N; j += i) {
            cnt[j]++;
        }
    }
    for (int i = 1; i < N; ++i) {
        cnt[i] += cnt[i - 1];
    }
}
 
int solve(int L, int R) {
    return cnt[R] - cnt[L - 1];
}
 
int main() {
    init();
    int L, R;
    cin >> L >> R;
    cout << solve(L, R) << endl;
    return 0;
}