埃氏筛法:从2开始,找到第一个没有被筛的数,把它标记为素数,然后把它的2倍、3倍……筛掉。
复杂度O(nlogn)
。
改进的埃氏筛法:从2开始,找到第一个没有被筛的数x
,把它标记为素数,然后把它的x
倍、x+1
倍……筛掉。
复杂度O(nloglogn)
。
线性筛:保证每个数都被它的最小素因子筛掉。
复杂度O(n)
。
埃氏筛法:从2开始,找到第一个没有被筛的数,把它标记为素数,然后把它的2倍、3倍……筛掉。
复杂度O(nlogn)
。
改进的埃氏筛法:从2开始,找到第一个没有被筛的数x
,把它标记为素数,然后把它的x
倍、x+1
倍……筛掉。
复杂度O(nloglogn)
。
线性筛:保证每个数都被它的最小素因子筛掉。
复杂度O(n)
。
阅读了《由感性认识到理性认识——透析一类搏弈游戏的解答过程》、《解析一类组合游戏》、《组合游戏略述——浅谈SG游戏的若干拓展及变形》这三篇论文,对组合游戏以及SG函数有了更深的理解。这篇文章摘下了这三篇论文的部分重要内容,以及部分我对组合游戏的理解。
组合游戏是满足以下一些性质的游戏:
Continue reading “组合游戏学习”这个题在bzoj上好像是个权限题,想做的可以去Vani的博客下载测试数据。
这里有题面。
简单叙述一下题意:
给你一个n个点、m条边的带权无向图,S点和T点,询问Q次删一条给定的边的S-T最短路。
其中 1<=n,m,q<=200000
。
ps. 1.这个题网上好多解法都是错的。2.这个题数据范围很大。
先求S到每个点的距离ds[i]
。如果ds[T]为inf的话,输出Q个无解好了。
然后再求每个点到T的距离dt[i]
。(用堆优化的Dijkstra即可。)