竞赛讨论区 > 【每日一题】1月7日题目精讲
头像
王清楚
编辑于 2021-01-07 11:07
+ 关注

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

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

图片说明

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

题解

作者:YangYL°

前言:

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

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(( + ) * 一个较小常数) 的。

不过上面分析的其实是程序最劣时间复杂度,实际上跑下来比这个要快得多。
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目1月14日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

(4) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐