秃头小白
秃头小白
全部文章
有关约数(质因...
01背包(1)
bfs(4)
dfs(6)
dfs序讲解(1)
Dijkstra算法 优先队列优化(2)
dp(7)
KMP(1)
LCA(4)
STL(1)
二分(5)
二分图(3)
二进制(1)
二进制枚举(3)
优先队列(1)
倍增(2)
分治(2)
前缀和与差分(3)
区间dp(11)
博弈论(1)
图(1)
并查集(5)
快速幂(1)
思维题(55)
数学题(7)
数论(2)
整除分块(数论)(1)
最小生成树(2)
栈(1)
树吧(5)
树状dp(1)
树状数组(2)
树状数组+dfs序(2)
模拟(4)
滑动窗口(4)
状压dp(1)
离散化+并查集(1)
离散化讲解及入门例题(2)
签到题(2)
素数筛(1)
线段树(10)
贪心(12)
逆元(1)
逆序对的三种求法(1)
题解(16)
高精度(8)
归档
标签
去牛客网
登录
/
注册
秃头小白的博客
小白世界
全部文章
/ 有关约数(质因数等)的基础数论
(共2篇)
阶乘分解
来自专栏
解题思路 正常思路:枚举1 ~ n,统计每个数的每个质因子的个数,但是时间复杂度为为O(n根号n)。正确思路:既然枚举数求质因子不行,那我们就枚举质因子求每个数含有此质因子的个数。 看似好像两个思路就是两层循环在内在外的关系,其实正确思路的时间复杂度为O(nlogn) n!的每一个质因子都不会超过n...
2020-11-21
2
824
Prime Distance
来自专栏
题目链接 http://poj.org/problem?id=2689 解题思路 前置知识:任何一个合数n都至少有一个质因子小于等于根号n;因为l和r的范围是1 ~ 2^31,范围太大,显然不能算出1 ~ 2^31的素数再枚举,但是发现r与l的差很小,1e6。我们的大致思路:标记l ~ r区间内的合...
2020-11-21
1
958