王清楚

编辑于 2021-01-07 11:07

+ 关注

【每日一题】1月7日题目精讲

题号 NC109065
名称 Numbers
来源 CF83D
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468

题解

作者：YangYL°

前言：

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

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

题意简述:

给定三个整数 $L$ , $R$ , $k$ ( $1<=L <= R <= 2 * 10 ^ 9 , 2 <= k <= 2*10^9$ )

你需要求出区间 $[L,R]$ 内，有多少个数 $i$ 满足: $k | i$ && 不存在一个 $j$ ∈ $[2,k - 1]$ 使得 $j | i$

其中 $k | i$ 表示 $i$ 被 $k$ 整除。

分析思路

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

为什么呢？

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

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

那么题意转化为:区间 $[L,R]$ 中有多少个数 $i$ 的最小质因数是 $k$

我们可以得到一个柿子：

$f(x,k)$ = $\lfloor \frac{x}{k} \rfloor$ $-$ $\sum f(\lfloor \frac{x}{k} \rfloor,i)$ (其中 $i$ <= $min(k - 1,\lfloor \frac{x}{k} \rfloor))$ 并且 $i$ 是一个质数。

对于柿子的解释：

$\lfloor \frac{x}{k} \rfloor$ 表示对于 $\frac{x}{k}$ 向下取整。

一开始的 $\lfloor \frac{x}{k} \rfloor$ 就表示我们假设所有 $k$ 的倍数的最小质因子都是 $k$ ，后面的 $\sum f(\lfloor \frac{x}{k} \rfloor,i)$ 就是减去所有不合法的答案，也就是 $k$ 的倍数中最小质因子不是 $k$ 的数的个数。然后至于为什么 $\sum f(\lfloor \frac{x}{k} \rfloor,i)$ 的括号里面是 $\lfloor \frac{x}{k} \rfloor$ ：

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

这里的 $\lfloor \frac{x}{k} \rfloor$ 也就是乘上的数的范围啦！于是得到了这个柿子。

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

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;
}

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

时间复杂度分析

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

考虑第一层向第二层的扩展：大概会有 $\sqrt{R}$ 个扩张。

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

这一行代码就告诉我们每一层最多就是循环 $\sqrt{x}$ 次

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

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

不妨这么想，首先，考虑有多少个点只能扩展出 $1$ 个，不难发现，有 $1,2,3$ 是只能扩展出 $1$ 个的 , 那么能扩展出 $2$ 个的就是 $4,5,6,7,8$ ，那么按照这个趋势下去，实际上，我们发现对于扩展 $k$ 个数的点，一共会有 $(k + 1) ^ 2 - k ^ 2 = (2 * k + 1)$ 个。
于是我们用这个规律来分析第二层向第三层一共有多少个扩展。