UOJ Logo matthew99的博客

博客

app管理器的乱搞经历

2015-08-11 09:06:46 By matthew99

昨天下午改完app管理器之后发现dwjshift的程序特别快,然而是个乱搞,便造了个数据hack了。之后觉得他的思路很有趣,便新建了一个dwjshift_fan的账号优化他的算法,代码风格都是我自己的然而并没有多少人认出那是我(大雾。

最后137ms过了那道题,我的hack数据也跑得很快,自己试了试好像也没能hack。算法大概就是每次用dfs实现的SPFA暴力找环然后确定方向之后缩起来,注意重边的处理。加了很多优化之后才跑到137ms。欢迎有兴趣的同学前来hack:http://uoj.ac/submission/24834

...妈妈我终于会做动态仙人掌IV了

2015-05-16 23:10:45 By matthew99

妈妈我终于会做动态仙人掌IV了!!

鼓掌熊

由于mx此时刚好正在滚粗搞文化课,为了战这道题,可谓历尽辛酸(大雾)。迟到缺交作业忘搞卫生已经把我罚得在班上没脸做人了。

傻逼mx还因为手算算错答案怀疑标程正确性制造了两个恶意hack。看来要被封号了QAQ

不能作为除出题人之外第一个AC的人真是太遗憾了,膜CHXER!

UPD:出了点奇怪的事情。

mx的仙人掌 题解

2015-03-27 11:59:14 By matthew99

题目地址

http://uoj.ac/problem/87

算法一

估计大家应该不会被仙人掌吓到而直接$\mathrm{gg}$了,至少先会考虑任意图的情况。

妈妈我不会处理图的问题怎么办?

有$5\%$的数据$n \le 7, \mathrm{tot} \le 7$,可以用各种方法(如枚举所有路径)水过去。

算法二

有$10\%$的数据$n, \mathrm{tot} \le 5000$。

最短路算法

由于时限和数据都很令人感动,这些数据其实用$\mathrm{dijkstra}$甚至$\mathrm{SPFA}$(我多良心没有卡哦!(大雾))都能跑得过去......

更好的做法

考虑仙人掌图的$\mathrm{dfs}$遍历树,有很多条前向边,每条前向边$x \rightarrow y$对应一个环,不妨设这个环的根为$y$,每当我们找到一条前向边$x \rightarrow y$时,通过从$x$不断回到$\mathrm{dfs}$树上的父亲直到到达$y$,我们可以取出这个环上所有点,并且容易得出环的长度,对所有点除了$y$以外的点都标记一下它所在的环编号。

$\mathrm{dfs}$完以后,对每个点考虑他到根的距离,如果他没有环标记那么距离就是父亲到根的距离加上自己到父亲的边的长度。否则就是他到环的根$y$的两条路径长度(一个是$\mathrm{dfs}$树上的距离(这个用两个点离根的距离减一减就求出来了),另一个是环的长度减去树上距离)中的较小值加上$y$到根的距离。

对每个询问的每个询问点,我们都遍历一遍,时间复杂度为$O(n\times \mathrm{tot})$。

算法三

有$10\%$的数据$Q \le 10$。我们考虑对每一次询问直接$\mathrm{dfs}$一遍求得答案。

用$\mathrm{maxlen}_x$表示从$x$出发到以$x$为根的子仙人掌(即在原图中删去$x$之后不与根相连的点和$x$的导出子图)的某个询问点的最短路的最大值(如果没有询问点可以设为-∞),对于$x$的某个$\mathrm{dfs}$树上的孩子$y$,如果从$x \rightarrow y$的边$e$是割边那么就直接用$\mathrm{maxlen}_y + w_e$更新$\mathrm{maxlen}_x$,$w_e$表示$e$的权值,否则如果$x$成为了边$e$所在环的根那么我们要把环取出来,直接枚举换上的点然后用他的$\mathrm{maxlen}$加上他到$x$的两条路径长度的最小值更新$\mathrm{maxlen}$即可。

考虑更新答案,所有询问点的$\mathrm{maxlen}$显然可以用来更新答案,对一个点的两个不同的子仙人掌(即在原图中删去$x$之后不与根相连的点的一个连通块和$x$的导出子图),他们的$\mathrm{maxlen}$之和加显然也可以用来更新答案(求出一个子仙人掌$y$的$\mathrm{maxlen}_y$之后,先用$\mathrm{maxlen}_y + \mathrm{maxlen}_x$更新答案,再用$\mathrm{maxlen}_y$更新$\mathrm{maxlen}_x$即可)。现在还需要考虑经过一个环的路径的情况。

经过一个环的最短路径一定是由两条环以外的路径(可以长度为0)和一条环上的路径组成,我们按顺序取出环上的边,并且复制一份接在后面,形成一条链。对于链上的点$i$,记$mathrm{len}_i$为链的头部到它的路径的长度,$\mathrm{val}_i$为它对应的点的$\mathrm{maxlen}$,那么经过这个环的最长的最短路径即为$\mathrm{max}\{\mathrm{val}_i + \mathrm{val}_j + \mathrm{len}_i - \mathrm{len}_j\}(0 \le \mathrm{len}_i - \mathrm{len}_j \le \frac{\mathrm{cirlen}}{2})$,其中$cirlen$表示该环的长度,容易用单调队列维护,时间复杂度为$O(Qn)$,如果用线段树时间复杂度为$O(Qn\log n)$。

算法四

对于树的情况,可以使用虚树。

虚树的建立方法之一是,对询问点按$\mathrm{dfs}$序排序,然后取出他们相邻节点间的$\mathrm{lca}$,接着再按$\mathrm{dfs}$序排序,接着扫一遍,维护一个栈,如果当前栈顶的节点是当前节点的祖先那么就连一条边,边权为它们之间的距离,否则将栈顶的节点弹出栈。这只是一种建立方法。

然后在虚树上$\mathrm{DP}$即可。

时空复杂度均为$O(n\log n)$(今后视tot = $O(n)$)

此外时间复杂度可以通过更大的代码复杂度降为$O(n\alpha(n))$或者$O(n)$,具体不再赘述,我多良心没有要求大家写这些算法哦!(大雾)。

算法五

对于树的情况,还可以用树分治解决。

一种较方便的树分治的做法是,先建立好树分治结构,然后对每一个询问,先将点去重。接着对于每一个树分治结构中的节点(对应一棵子树$T$),我们只考虑该询问中所有在$T$中的点。直接用两个属于不同子树的点到根的距离和的最大值更新答案即可(要注意判一下询问点是根的情况)。接着对于它的每一个孩子节点,递归处理下去,注意我们只要保留该询问中在这个孩子节点中的点。

但是这个做法由于要预先存储结构,时间空间常数都比较大。

还有一种做法是,询问和树一起分治,这个很好理解,无非就是把两个过程合并了,每一次要处理的是一棵子树和一个询问序列,这个序列只保留所有存在询问点在该子树中的询问,并且每个询问只保留在该子树中的询问点,然后处理询问的方法如同前面所述。

时空复杂度均为$O(n\log n)$。

UPD:树上迭代两次求最远点即可,最远点可以直接枚举然后$\mathrm{lca}$,呜呜呜我出题的时候怎么就脑抽了,30分送大家吧,前面的算法就当做口胡......

算法六

对于树的情况,如果你只会虚树或者树分治,对于仙人掌你肯定也只能这么做了。

如果我们能建立“虚仙人掌”,肯定可以解决这个问题。思考熊

我们想一想就能想清楚虚仙人掌的一种最笨但是也绝对正确并且可以通过这题的建立方法,先按$\mathrm{dfs}$序排序,再求出相邻节点间的$\mathrm{lca}$(注意这里$\mathrm{dfs}$序和$\mathrm{lca}$都是在它的$\mathrm{dfs}$遍历树上做,后面的深度也是),接着我们取出每一个点所在环的根和环上最深的点,再排序并取一遍相邻节点$\mathrm{lca}$,然后建出$\mathrm{dfs}$树上的虚树,接着再每个环的最浅的点和最深的点之间连边,边权为它们原先连的边的权值(它们原先显然一定连了边),由于我们要求的是最短路径,其实这里连它们之间在环上走的两条路径的较小值也没有关系,不会对任何最短路径造成影响,这一个画一画图就知道了。

根据上述结论,连虚树上的边时,可以将虚仙人掌上的环边和树边一视同仁,统统连它们两个端点在原仙人掌上的最短路径长度。但是这个最短路径长度和树上不同,树上可以直接用离根的距离减一减,仙人掌上就不是这么简单了,离根的最短路长度不具有可减性。是,我们可以用动态仙人掌。但是这样代码复杂度太高。我们考虑一下,如果树上有一个值也不具有可减性,比如路径边权最小值,你会怎么弄?一种方法就是倍增。对仙人掌也这么弄,考虑动态仙人掌维护生成树法的思想,我们记录每个点到它第$2 ^ i$级祖先的最短路长度,同时如果有一个环不完全包含这条路径,且包含第$2 ^ i$级祖先的父亲(显然这个祖先如果是根就不可能存在满足条件的环),那么我们就记录一下这条路径上深度最大的在这个环上的点,合并的时候就根据这个环是走树边还是走非树边来求出最短路,非常简单。

UPD:好像可以记录到根的距离,然后用特殊的方法处理一下就可以直接减了。总之实现上有各种技巧优化时间复杂度和代码复杂度,感觉标程就是个逗比啊TAT......

实际上,std的方法和上述方法有细节上的差异,如果$x$本身连了一条非树边,包含了整个路径及$2 ^ i$级祖先的父亲,那么他也将被记录,但是这样合并的时候将会多出一些小麻烦,因为一个环可能会更新一条路径两次,用后一次更新覆盖掉前一次更新即可。但是如果不用这个方法,$\mathrm{dfs}$树的叶子节点连接的非树边也要特判。不过这些东西都是一些细节问题,稍微处理一下即可。

总之这个算法可以非常愉悦的跑出100分, 时空复杂度均为$O(n\log n)。$鼓掌熊

提交记录在这里

算法七

对于树分治,我们显然也可以想办法把它搞到仙人掌上,也就是用仙人掌分治来解决问题,实现细节和树分治大同小异,每一次去掉一个点时,先把它弄成仙人掌的根,然后断开它连的所有割边,以及所有它所在环的环边,每一次选一个进行上述操作后,剩下来的子仙人掌中大小最大的最小的点来分治即可(其实为了方便我写的程序不一定能取出最小,但绝对剩下来的子仙人掌中大小最大的不超过$\frac{n}{2}$)。

处理每个询问时,根可能连着不少的环。对一个点(除了根),如果在某一个环$C$上或者某一个在$C$上的点(除了根)的子仙人掌,那么称这个点属于环$C$。,直接用两个属于不同子仙人掌或者环的点到根的距离和的最大值更新答案即可(同样要注意判一下询问点是根的情况)。但是我们还要注意属于同一个环但不是环上同一个点的子仙人掌的点,他们两两之间也要更新答案,这个用单调队列很好解决。

时空复杂度均为$O(n\log n)$。鼓掌熊

我用算法七写的程序,比算法六的程序常数大了很多。我估计树分治应该常数也会比虚树大很多(大雾)。但鉴于我是个常数渣,我的程序的运行时间仅供参考。

UPD:$\mathrm{extra\ test}$把这个程序卡掉了,卡常数中T_T......大家可以争取比我先卡过去然后尽情地来婊出题人的常数吧!

UPD:卡过去了,提交记录在这里,从不到8K卡到9K多,感觉有点爽。

解法八

松爷给出了另外一种解法,详见http://wangyisong1996.is-programmer.com/user_files/wangyisong1996/File/zjoi2015/cactus-slides/wys-cactus-slides.html#/6

AC代码:

http://uoj.ac/submission/13387

http://uoj.ac/submission/13388

第一份的空间复杂度是$O(n\log n)$,比第二份多一个$O(\log n)$,但代码量更小。

此外,仙人掌分治和虚仙人掌都可以在线,前者在线情况应该会TLE甚至可能MLE(至少我的写法如此= =b),后者本身就可以在线。这种做法就没什么简单办法做到在线了= =b。

解法九

waltz给出了另外一种解法:http://uoj.ac/submission/13649

时间空间代码量都完虐我啊orz......

这个做法是对每个环,新建一个点,向环上每个点连长度为它到环的根的最短路径长度的边,如果对新树dfs,那么每个点到它的任意非新建祖先的最短路径长度就是它们之间在树上的距离,对于lca不是新建点的两个点最短路长度就是它们之间在树上的距离,是新建点的话,在树上的距离也不会小于真实距离,但我们可以单独取出环再单调队列来解决环的问题。这道题成功降级为符合人民大众胃口的既无思考难度也无代码难度的傻逼题。跪烂waltz!

基于这个思路,也许很多仙人掌上问题可能会有更简单的做法?思考熊

乱搞

我们发现对于树的情况,直径就是任取一个点$a$,求出他的最远点$x$,再求出最远点$y$,$x$到$y$的距离,应用到仙人掌上是不正确的。因为一个大环连上一条小边,只有$a$取到$O(1)$个点时才能求出答案,对于其他点就算不断找最远点迭代∞次答案也不正确。(想知道这个算法能拿多少分吗?写写就知道!坏笑熊)

另外我们还可以多次枚举点做根,然后设法求得经过根的最长路径,由于答案路径可能很长,一旦取到了一个答案路径上的点做根就可以求出正确答案。但是一旦答案路径比较短,这个算法就不靠谱了。并且这个算法没法较好的判断是否已经是当前答案已经正确。

如果你通过各种方法乱搞过了,你就可以好好感受一下$\mathrm{extra\ test}$和$\mathrm{hack}$的威力了。坏笑熊

后记

其实这个题如果出成每对点的最短距离和的话,是可以避免乱搞的,而且不难实现,但是由于奇怪的原因,我没有把它改成这样。

在出题人想出一个原始的算法之后,算法又其他人不断被改进,长江后浪推前浪。感觉我从这道题的出题经历中感受到了科技的进步。捂脸熊

5s的时限真是太良心了233,主要是为了欢迎各种奇葩做法。

mx的组合数 题解

2015-03-27 11:58:56 By matthew99

题目地址

http://uoj.ac/problem/86

QAQ我把这题出出来之后,发现以前有一道几乎一样的题,而且我还A过!感觉自己记性真的有点好......捂脸熊

算法一

对于$10\%$的数据,$n, l, r \le 1000$。因此我们直接暴力枚举$x$,然后暴力求组合数即可。

如果你不会模意义下的除法,可以用杨辉三角打出前$1001$行,然后直接查询。

如果你既不会除法也不会杨辉三角(居然能看懂题目?),存在$5\%$的数据$n, l, r \le 10$,答案可以用各种方法直接算出来= =b。

算法二

对于$20\%$的数据,$n, l, r \le 100000$,我们可以用公式 ${n + 1 \choose m} = \frac{n + 1}{n - m + 1}{n \choose m}$递推出所有组合数。

算法三

对于另外$20\%$的数据,$r - l \le 10000$,我们暴力枚举$x$之后,组合数计算可以根据Lucas定理计算,但是直接枚举计算是会超时的。

首先我不知道有多少人听到这个定理后想到的是这个公式

${a \choose b} \bmod p = {\lfloor\frac{a}{p}\rfloor \choose \lfloor\frac{b}{p}\rfloor}{a \bmod p \choose b \bmod p} \bmod p$

而不是

${a \choose b} \bmod p = \prod\limits_{i \ge 0}{a_i \choose b_i} \bmod p$,其中$a_i$表示$a$在$p$进制下从较低位数起的第$i$位。

前者和后者的等价关系很显然。

用第二个公式,我们对每一位都预处理出所有组合数,复杂度为$p \times 位数$,然后枚举$x$之后可以用$O(位数)$的时间直接查询每一位的组合数值然后算出来,如果每次重新计算$x$的$p$进制,复杂度为每次$O(位数 ^ 2)$,如果每次加$1$并进位,还可以做到$O(位数)$,两种复杂度都可以轻松通过这一部分数据。

算法四

首先问题容易转化为小于等于$r$的$x$个数减去小于等于$l - 1$的$x$个数,我们只要考虑形如$x \le bound$的限制即可。

算法三给了我们启发,我们应该从$p$进制下考虑。思考熊

很容易设计出数位DP的状态和转移方程:

$g[i, j]$表示从低位开始前$i$位任意且值为$j$的方案数。 $f[i, j]$表示从低位开始前$i$位对应的$p$进制数不超过$bound$的前$i$位对应的$p$进制数且值为$j$的方案数。

假设$n$的第$i + 1$位为$y$,$bound$的第$i + 1$位为$w$,枚举第$i + 1$位的值$x$,若${x \choose y} = z$则

$g[i + 1, jz \bmod p]$ += $g[i, j]$

若$x \lt w$则$f[i + 1, jz \bmod p]$ += $g[i, j]$

若$x = w$则$f[i + 1, jz \bmod p]$ += $f[i, j]$

时间复杂度为$O(位数 \times p ^ 2)$,结合算法三可以获得$70$分,事实上前$40$分的答案比较稀疏,通过常数优化或许可以直接通过。

算法五

由于$p$是质数那么一定存在原根$g$,在算法四的转移方程中,若$j$,$z$均不为$0$,那么一定存在原根$g$下的关于模$p$的离散对数,通过取离散对数再根据费马小定理,很容易将转移方程中的$jz \bmod p$转化为$g ^ {(ind(j) + ind(z)) \bmod (p - 1)} \bmod p(ind(x)$表示$x$在原根$g$下关于模$p$的离散对数),从而转移方程可化为卷积的形式,FFT即可。

对于$j = 0$或者$z = 0$的情况,我们可以在转移中忽略,先将$1 \rightarrow p - 1$的答案统计出来,然后用总数减掉即可。

由于模数的特殊性,可以用数论变换解决。

于是这题被完美解决啦。

提交记录在这里

鼓掌熊

p = 2挂掉啦!

注意枚举原根要从$1$开始而不是从$2$开始

此外数组要开到$100$左右,而不是$30$或者更少。

太麻烦了

请问你们这些说麻烦的人,都为什么会觉得麻烦?

求原根太麻烦

这题的$p$很小,加上原根很多,直接暴力从$1$到$p$枚举然后直接枚举$1$到$p - 2$次方看有没有提前出现$1$即可,连$p - 1$的约数都不用枚举!捂脸熊

我不想写离散对数的大步小步算法

还是那句话,这题的$p$很小,直接预处理出所有的数的离散对数值即可。

此外逆元也可以预处理,并且还可以使用$O(p \log p)$的算法,不一定要写线性算法。

我不想写高精度

你可以用自带高精度的语言比如$\mathrm{python,java}$等,当然要注意常数问题。

如果你只会$\mathrm{C}$++,UOJ支持$\mathrm{C}$++的__$\mathrm{int128}$(__$\mathrm{int128}$_$\mathrm{t}$),可以避免高精度。超人熊

使用方法可以参考这个提交记录:__$\mathrm{int128}$(__$\mathrm{int128}$_$\mathrm{t}$)

π(n)的计算

2015-03-11 09:23:26 By matthew99

本文中的做法已经被艹了,大家想追求最优算法的话请不要阅读本文。

$\pi(n)\ne\pi n$,更不是$3.141592655\cdots (n)$(←_←),而是小于等于$n$的质数个数,$n$可以是任意实数。

普通算法

直接用线性筛就可以做到$O(n)$。

逗比算法

用$O(n\log n)$的筛法!

不对我会$O(n\log \log n)$(只用质数筛就是$O(n\log\log n)$)

帅气的算法一

根据容斥原理可得,所有小于等于$x$的数中,不能被$n$个不同的质数$p_1, p_2,\cdots,p_n(p_i是第i个质数)$中的任何一个整除的个数是

$\lfloor x\rfloor - \sum\limits_{i}\lfloor\frac{x}{p_i}\rfloor + \sum\limits_{i\lt j}\lfloor\frac{x}{p_ip_j}\rfloor - \sum\limits_{i\lt j\lt k}\lfloor\frac{x}{p_ip_jp_k}\rfloor + \cdots$

若$n = \lfloor \sqrt x \rfloor$这个数显然就是$\pi(n) - \pi(\sqrt n) + 1$。

设$\Phi(x', n')$表示小于等于$x'$的数中($x'$可以是任意实数),不能被$n$个不同的质数$p_1, p_2,\cdots,p_n$中的前$n'$个整除的个数,则根据上面的式子容易推得

$\Phi(x', n') = \Phi(x', n' - 1) - \Phi(\frac{x'}{p_{n'}}, n' - 1)$

递归边界为

$\Phi(x', 0) = \lfloor x'\rfloor$

这个考虑一下上式中每一个$p_k$对式子的贡献即可。

注意到在递归过程中,第一个参数永远是$\lfloor\frac{x}{a}\rfloor$,$a$是某些因数的乘积,而即便$a$取所有值,上述值也不超过$O(\sqrt x)$个,第二个参数显然也是$O(\sqrt x)$个,这么一来如果加上记忆化或者直接递推,时间复杂度上界是$O(x)$,或许存在更低的上界,比如比线性低一个$O(\log x)$或者$O(\log log x)$?(大雾)。

UPD:任之洲同学指出这个算法的计算量实际上是$O(\frac{x}{\log x})$,且给出了一个$O(\frac{n ^ \frac{3}{4}}{\log n})$的做法,并且可以推广到质数的$k$次方和的情况。看起来本文没有什么存在的意义了(雾)。

帅气的算法二

令$P_k(x, n)$表示小于等于$x$的数中恰好含有$k$个大于$p_n$的(可以相同的)质因子且不含有小于等于$p_n$的质因子的个数,又不妨令$P_0(x, n) = 1$,则:

$\Phi(x, n) = \sum\limits_{k = 0}^{+∞}P_k(x, n)$

令$y = \sqrt[3]{x}$,$n = \pi(y)$,则$P_k(x, n) = 0(k \ge 3)$。

而显然有

$P_1(x, n) = \pi(x) - n$

$P_2(x, n) = \sum\limits_{y \lt p \le \sqrt x, p是质数}{\pi(\frac{m}{p}) - \pi(p) + 1}$(设$x = ab$($a, b$是质数)是满足条件的数,那么当且仅当$p = min\{a, b\}$时统计了$x$一次)

所以$\Phi(x, n) = 1 + \pi(x) - n + (\sum\limits_{y \lt p \le \sqrt x}{\pi(\frac{m}{p}) - \pi(p) + 1})$

移项得

$\pi(x) = \Phi(x, n) - 1 + n - (\sum\limits_{y \lt p \le \sqrt x}{\pi(\frac{m}{p}) - \pi(p) + 1})$

预处理$\pi(1)$到$\pi(x ^ \frac{2}{3})$的值,那么除了$\Phi(x, n)$之外,其他的项都可以在$O(n ^ \frac{2}{3})$内求出。

对于$\Phi(x, n)$,由于$n = O(x ^ \frac{1}{3})$,而第一个参数上界是$O(x ^ {\frac{1}{2}})$,因此总的复杂度不超过$O(x ^ \frac{5}{6})$,且有可能更优?(大雾)

总之还是做到比线性低啦!

鼓掌熊

实现

实现成功后我们发现,正如题目中所述,时间复杂度只是个上界,实际上这个算法跑的很快。以下是我用来计算$\pi(10 ^ 9)$的代码,实际上$calc$中的不同参数只有不到70万个,比理论值$10 ^ {7.5}$不知道少到哪里去了,因此如果有更好的复杂度上界,请告诉我。

变量定义和该文章中的定义有所不同,请大家注意分别。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <ctime>
#include <cassert>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>

#define REP(i, a, b) for (int i = (a), _end_ = (b); i != _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long LL;

const int maxn = 1e6, max0 = 1e5;

int sum[maxn + 5];
int prime[max0 + 5];
int pn = 0;

LL n = 1000000000LL;

int Max = -1;

__gnu_pbds::gp_hash_table<int, int> id;

LL a[40000][1000];
int an = 0;

LL calc(const int &n, const int &x)
{
    if (x < 0) return n;
    if (!id[n]) id[n] = ++an;
    int tmp = id[n];
    if (a[tmp][x] != -1) return a[tmp][x];
    return a[tmp][x] = calc(n, x - 1) - calc(n / prime[x], x - 1);
}

int main()
{
    memset(a, -1, sizeof a);
    for (int i = 2; i <= maxn; ++i)
    {
        if (!sum[i]) 
        {
            if ((LL)i * i * i <= n) Max = pn;
            prime[pn++] = i;
        }
        sum[i] = sum[i - 1] + !sum[i];
        for (int j = 0; j < pn && prime[j] * i <= maxn; ++j)
        {
            sum[i * prime[j]] = 1;
            if (!(i % prime[j])) break;
        }
    }
    LL ans = calc(n, Max) + Max;
    for (int p = Max + 1; (LL)prime[p] * prime[p] <= n; ++p) ans -= sum[n / prime[p]] - sum[prime[p]] + 1;
    cout << ans << endl;
    return 0;
}

该程序的运行结果是50847534,与维基百科上的一致。在本机上(开启O2优化)运行时间为$53\mathrm{ms}$,主要耗时依旧在$\Phi$函数的计算中。

内存的话凑合着看吧,我又没说要直接用这个当模板交题。坏笑熊

参(chao)考(xi)文献

Prime-counting function

在该条目中还提到了更好的算法,有兴趣的人可以去深入研究。

UPD:本文章中的算法已被完艹 ...更多内容参见π(n)的计算++

...妈妈我终于会玩新年的魔塔了!!

2015-03-06 01:20:09 By matthew99

小学的时候玩了那么久的魔塔, 果然还是有点用的2333333(大雾)

鼓掌熊

已未年第一篇博客,祝大家新年快乐

2015-02-19 00:04:28 By matthew99

愿新的一年里,大家每场比赛都能取得理想的成绩。看题就能秒,写题就能对。人人都能拿金牌!

共 17 篇博客