P9611 题解

· · 题解

题目大意

从题目可知，本题要求求出l \sim r的因子个数和。

题目分析

我们可以将这个问题分解为两个问题，变成求1 \sim r的因子个数和减去1 \sim l-1的因子个数和，然后我们考虑如何求1 \sim n的因子个数和

首先，如果正着做很难的话，我们可以考虑反着做。

对于一个数x，因为在1 \sim n中，有\lfloor n \div x \rfloor个数能被x整除，所以它对于因子个数的贡献为\lfloor n \div x \rfloor。

根据这个原理，我们可以写出一个时间复杂度为\mathcal{O}\left(n\right)的TLE程序：

#include<bits/stdc++.h>
#define int long long 
const int N = 1e5+5;
const int Mod = 1e9+7;
using namespace std;
int l, r;
int f(int n)
{
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        cnt += n / i;
    }
    return cnt;
}
signed main()
{
    cin >> l >> r;
    cout << f(r) - f(l - 1) << endl;
    return 0;
}

看来我们要把时间复杂度降到\mathcal{O}\left(\sqrt n\right)才可以。

可以想到，对于每一个数，他的因数必然是成对的（平方数除外），那么我们只需要遍历到\lfloor \sqrt n \rfloor，最后再乘以二即可。但是我们会发现，这样计算的结果比正确结果大很多，为什么呢？因为会有重复。所以我们要把重复的减去，这样才可以得到正确的结果。

那么现在我们要考虑哪些部分会重复。

我们以n为9为例：

数字 因数
1 1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9

我们的贡献统计是这样的：

数字 贡献数字对
1 1\times\red1,1\times2,1\times3,1\times4,1\times5,1\times6,1\times7,1\times8,1\times9
2 \red2\times\red1,2\times\red2,2\times3,2\times4
3 \red3\times\red1,\red3\times\red2,3\times\red3

通过观察重复的标红部分，我们发现每个数刚好重复了\lfloor \sqrt n \rfloor次！为什么会这样呢？因为每一个数乘上另外一个数，如果反过来还在表里面，那么就会重复。在表里面有\lfloor \sqrt n \rfloor个数，每个数会重复\lfloor \sqrt n \rfloor次，所以总共会重复\lfloor \sqrt n \rfloor\times\lfloor \sqrt n \rfloor次。

于是我们便可以完成最后的代码：

AC Code

#include<bits/stdc++.h>
#define int long long 
const int N = 1e5+5;
const int Mod = 1e9+7;
using namespace std;
int l, r;
int f(int n)
{
    int cnt = 0, sqr = sqrt(n);
    for(int i = 1; i <= sqr; i++)
    {
        cnt += n / i;
    }
    return cnt * 2 - sqr * sqr;
}
signed main()
{
    cin >> l >> r;
    cout << f(r) - f(l - 1) << endl;
    return 0;
}