首页 > Numbers
开通博客写题解
头像 MYCui_
发表于 2020-12-26 17:13:24
CF83D[numbers] 前言： 很好的一道数学容斥题。考察时间复杂度的分析。 2021/1/6 update: 因为笔者 , 一开始的做法比较劣（于是将题解重写了） 题意简述: 给定三个整数 ,, () 你需要求出区间内，有多少个数 满足: && 不存在一个 ∈ 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 shyyhs
发表于 2021-01-06 20:20:13
前言: 这题难点在于复杂度分析. 实现: 首先很容易想到k假如不是质数答案为0.因为假如k不是质数,那么它一定可以写成比它小的数相乘.其次假如答案可行,必定是大于等于k的质数的乘积的形式.因为假设不是比k的质数乘积,就是利用了到的质数.这是不行的.有了这两点,暴力的代码应该是都会写的..区间的就等于 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 issue是云哥的小迷×呀
发表于 2021-01-06 21:53:47
传送门 由于不能包括的因子 所以得到的数字分解质因子后必定都是大于等于的质因子 那么一个数的质因子不会个...好像没什么用 搜索的复杂度是上天的。 那就套路的容斥,求符合条件的就是求符合条件的 那么如何求的方案数.... 首先是倍数的数有个,在这基础上需要进行容斥,因为有数拥有比小的因子的同时也拥有 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 熠丶
发表于 2021-01-07 14:13:18
题意： 求在区间 内满足 ， 且对于任意 都不满足 的数 的个数。 做法：分块+数学 思路： 1.求区间满足个数可以转化为的个数减去 2.由题意易得k一定是个质数，否则一定不存在满足不满足 的数 因为k会被 整除，所以一定 3.同时i要同时满足是k的倍数且k是最小公因数 4.所以综上所述可 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”