CF83D [Numbers] 题解

CF83D[numbers]

前言：

很好的一道数学容斥题。考察时间复杂度的分析。

2021/1/6 update: 因为笔者 , 一开始的做法比较劣（于是将题解重写了）

题意简述:

给定三个整数 ,, ()

你需要求出区间内，有多少个数 满足: && 不存在一个 ∈ 使得

其中 表示 被 整除。

分析思路

我们发现一个很显然的性质。倘若 不是质数，那么最后的答案肯定是

为什么呢？

因为倘若 不是质数，假若 那么肯定存在一个不等于 的大于等于 的因子 也满足 ， ，这时候肯定没有一个满足条件的 ，所以最后答案是

因此我们只需要考虑 为质数的情况。

那么题意转化为:区间 中有多少个数 的最小质因数是

我们可以得到一个柿子：

= (其中 <= 并且 是一个质数。

对于柿子的解释：

表示对于 向下取整。

一开始的 就表示我们假设所有 的倍数的最小质因子都是 ，后面的 就是减去所有不合法的答案，也就是 的倍数中最小质因子不是 的数的个数。然后至于为什么 的括号里面是 ：

实际上我们枚举的是 的倍数，也就是 乘上一个数，我们实际上只需要判断乘上的那个数的最小质因数大于等于 即可。

这里的 也就是乘上的数的范围啦！于是得到了这个柿子。

另外这道题目的一个技巧还有差分，也就是对于区间 算答案可以算 的答案 - 的答案。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
bool GetPrime(int k) { //O(sqrt(n))判断质数相信大家都会
    for(int i = 2 ; i <= sqrt(k) ; i ++)
        if(k % i == 0) return 0;
    return 1;
}
int GetAns(int x,int k) { //上面提到的计算f(x,k)的函数
    if(GetPrime(k) == 0) return 0;//如果 k 不是质数，显然答案为0
    int sum = x / k;//假设全是k的倍数
    for(int i = 2 ; i <= min(x / k,k - 1) ; i ++)
        sum -= GetAns(x / k,i);
    return sum;
}
signed main() {
    int l , r , k ;
    cin >> l >> r >> k;
    cout << GetAns(r,k) - GetAns(l - 1, k);
    return 0;
}

短小，跑得飞快的！看得你是不是懵懵的？为什么这个玩意看起来这么暴力还这么快！

时间复杂度分析

关于这个时间复杂度的分析，由于是递归的形式，不妨按照类似于分析“搜索树”（这里指的是分析搜索复杂度的方法）的方式来按层分析，“搜索树”多少个点，时间复杂度就大概是多少。

考虑第一层向第二层的扩展： 大概会有 个扩张。

for(int i = 2 ; i <= min(x / k,k - 1) ; i ++)

这一行代码就告诉我们每一层最多就是循环 次

也就意味着第二层极限情况下大概会有 个扩张

第二层向第三层的扩张呢？有人可能会说是 个扩张，其实这么说是不严谨的，因为实际上，有很多点扩张实际上达不到 个。那么到底是多少呢？

不妨这么想，首先，考虑有多少个点只能扩展出 个，不难发现，有 是只能扩展出 个的 , 那么能扩展出 个的就是 ，那么按照这个趋势下去，实际上，我们发现对于扩展 个数的点，一共会有 个。
于是我们用这个规律来分析第二层向第三层一共有多少个扩展。

那么，对于第二层一共会有多少个扩展呢？

也就是 + + + + ...... +

现在我们的目标就是求出这里的 最大是多少。

不难得出，这里的 最大是 (在 的情况下) 那么上面的柿子我们就可以估算是

第三层向第四层的扩展呢？实际上这一层的扩展数量是很小的，在庞大的 面前，我们可以将其忽略不计(其实下面的层数大概把这个 乘以了一个 )。

因此，笔者估计总的复杂度大概就是 O(( + ) * 一个较小常数) 的。

不过上面分析的其实是程序最劣时间复杂度，实际上跑下来比这个要快得多。