题解创新

Euler_Pursuer

2018-09-05 21:19:51

Solution

# 题目解答 ## 比赛解答 [比赛解答链接](https://www.luogu.org/blog/20782/solution2) $O(\sqrt{B})$的原创解答在本博客最下面。 各位也可以参考一下另一位大佬写的$O(\sqrt{B})$的做法:应该就在这里,不过思路和我不一样。 鉴于各位懒得打开比赛解答,现在贴出$O(B)$的解法,**解答来自出题人**。 ### 冷静分析 第一时间想到的是内部分块做法,外部线性暴力,不过细细一看,这绝对会超时的啊(你自己都说暴力了)!因此我们需要一个线性做法。 那么我们就需要将式子变形了。 $$\sum^{B}_{i=A}\sum^{i}_{j=1}\left \lfloor \frac{i}{j} \right \rfloor \times \left ( -1 \right )^j =\sum^{B}_{i=1}\left ( \left ( -1 \right )^i \sum^{B}_{j=A} \left \lfloor \frac{j}{i} \right \rfloor \right )$$ 注意到式子中,我们把$-1$提出来了,为了使式子等价于原来的式子,我们不得不给式子做一个大手术。因为$-1$提前了,那么它的幂次只能是$i$,于是我们将$i$和$j$的意义替换,变换式子使得其等价于原来的式子。其中注意$i>j$时,分式向下取整得$0$,对答案无影响,所以这两个式子是等价的。 看到这里,你可能还是不知道怎么得到线性做法,我们就这样看: $$\sum^{B}_{i=1}\left ( \left ( -1 \right )^i \sum^{B}_{j=A} \left \lfloor \frac{j}{i} \right \rfloor \right )=\sum^{B}_{i=1}\left ( \left ( -1 \right )^i \left ( \sum^{B}_{j=1} \left \lfloor \frac{j}{i} \right \rfloor - \sum^{A-1}_{j=1} \left \lfloor \frac{j}{i} \right \rfloor \right ) \right )$$ 现在$i$是比较稳定的了,因为当$i$取一个值时,而$j$是连续递增的,那么向下取整可以得到连续$i$个的向下取整的相同的值。 举个例子吧,当$i=3$时,假设$j$从$1$逐一递增到无穷,我们会得到: $$0,0,1,1,1,2,2,2,3,3,3,\cdots $$ 那么我们就可以在$O(1)$的常数时间内算出里面的和式差,最终我们就得到了时间复杂度为$O(B)$的算法。 当然,由于$B$有点大,因此我们需要稍微注意一下常数问题。 不过,在写程序的时候,要注意考虑前面的$0$的个数是$i-1$个的。但是总体还是有规律可循,具体看我的程序。 ### 程序实现 ```cpp #include <cstdio> int main() { int a, b; long long ans = 0, r, s, t; scanf("%d%d", &a, &b); for(register int i = 1; i <= b; i += 1) { r = a / i - 1;//因为最后一项长度不定,所以我们确定倒数第二项 s = (a - r * i - i) * (r + 1);//计算最后一项的长度并求和 r = (r + 1) * r / 2 * i;//前面项的和 t = s + r; //同理可得 r = (b + 1) / i - 1; s = (b + 1 - r * i - i) * (r + 1); r = (r + 1) * r / 2 * i; if(i & 1) ans -= s + r - t; else ans += s + r - t; } printf("%lld", ans); return 0; } ``` 最大耗时点耗时:237ms。 本人经过摸索,终于写出了根号级的做法。 ## 极速解法(原创) 当然,和式还是原出题人给的。 ### 冷静分析 现在将那个和式进行变换: $$\sum^{B}_{i=1}\left ( \left ( -1 \right )^i \left ( \sum^{B}_{j=1} \left \lfloor \frac{j}{i} \right \rfloor - \sum^{A-1}_{j=1} \left \lfloor \frac{j}{i} \right \rfloor \right ) \right )=\sum^{B}_{i=1}\left ( \left ( -1 \right )^i \sum^{B}_{j=1} \left \lfloor \frac{j}{i} \right \rfloor \right ) - \sum^{A-1}_{i=1}\left ( \left ( -1 \right )^i \sum^{A-1}_{j=1} \left \lfloor \frac{j}{i} \right \rfloor \right )$$ 我们可以对最外层的和式进行分块运算。 我们只需分成$4$组进行求和即可,也就是将其分为奇偶和左右部分即可(方便快速高斯求和)。 那么分块具体如何实现呢? 我们发现内部都是有秩序的,虽然将外层的$i$以不同的值写出,同类合并之后我们会发现有点混乱,但是并非无迹可寻! 因为注意到$\left \lfloor \frac{j}{i} \right \rfloor$在某几种$i$的值中(连续的、差为$2$的$i$值),如果组成的数的个数不变(比如都有$1$到$9$),那么除最后一个数(前面的例子的$9$),其他数的变化都是**同规律线性的**(根据比赛题解中提到的结论可得),可以用高斯求和公式算出来。 而组成的数个数不变,当且仅当$\left \lfloor \frac{j}{i} \right \rfloor$中$j$取最大值时该式得到的值不变。 就比如上面提到的那个$9$,因为随着$i$的变化,比$9$小的值都会越来越多,而$9$就会被压出去(可以说是溢出吧2333),毕竟序列长度只有这么长。 而这个值(例如那个$9$)的变化也是线性的!因为前面是线性递增,那么上述的$9$的个数就会线性递减。 那么线性的都可以算出来,仅对最大值的变化讨论即可。而最大值的变化恰恰是有分块的属性(这个不难证明,大家思考一下),于是我们通过内部常数时间,外部分块时间即可算出答案。 严格来说,根号外面至少还有$4$的常数,但是还有可以优化的地步——常数优化(~~蒟蒻我太懒了~~)。而时间复杂度还是$O(\sqrt{B})$的,所以很快就能通过。 ### 程序实现 ```cpp #include <cstdio> int a, b; //对比O(B)的代码,其实只是加了一些高斯求和罢了 inline long long getans(int f) { int rr, q, delta; long long ans = 0, r, r_, s, t, l; for(register int i = (f ? 1 : 2); i <= a; i = q + 2) { rr = a / i; q = a / rr; if((q & 1) && !f)//要偶数却是奇数 q ^= 1; else if(!(q & 1) && f)//要奇数却是偶数 q -= 1; delta = (q - i >> 1) + 1;//中间长度 r = a / i - 1;//因为最后一项长度不定,所以我们确定倒数第二项 l = a + 1 - r * i - i; s = (r + 1) * (l - (delta - 1) * (r + 1)) * delta; //分块的最后一项求和 r_ = r;//记录 r = (r + 1) * r * i >> 1;//前面项的和 r = r * delta + ((1 + r_) * r_ >> 1) * ((delta - 1) * delta); //增加的值 t = s + r; if(f & 1) ans += t; else ans -= t; } for(register int i = (f ? 1 : 2); i <= b; i = q + 2) { rr = b / i; q = b / rr; if((q & 1) && !f)//要偶数却是奇数 q ^= 1; else if(!(q & 1) && f)//要奇数却是偶数 q -= 1; delta = (q - i >> 1) + 1;//中间长度 r = b / i - 1;//因为最后一项长度不定,所以我们确定倒数第二项 l = b + 1 - r * i - i; s = (r + 1) * (l - (delta - 1) * (r + 1)) * delta; //分块的最后一项求和 r_ = r;//记录 r = (r + 1) * r * i >> 1;//前面项的和 r = r * delta + ((1 + r_) * r_ >> 1) * ((delta - 1) * delta); //增加的值 t = s + r; if(f & 1) ans -= t; else ans += t; } return ans; } int main() { scanf("%d%d", &a, &b); a -= 1; printf("%lld", getans(1) + getans(0)); return 0; } ``` 单点最大耗时:3ms(由于新测评机的缘故,至少都是2ms的点,应该可以0ms的,没赶上时机哎)。 # 个人感慨 其实上午根据原题解的式子就想到了这个方法(不过也要感谢另一位也是根号解法的大佬提了一下有根号的做法),很感谢原题解作者的化简式,不然我也不会想到。不过我在写程序的过程中也出现了很多小插曲,比如刚写完函数老师就点了集体关机,然后还原GG。不过还好我记得这个方法,然后又写了一下午,调试了大概一个小时还不对,当时是绝望的。然后我发现我智障的把$p$写成了$i$导致奇偶错乱,改了之后大部分数据都过了。进一步我将$a$的那部分有一些与$b$扯上关系的东西改成了$a$(目前还未证明为什么不对)。 总之我想说的是:**成功贵在坚持不懈**! # 写在最后 感谢比赛举办者提供的题目和题解,感谢各位阅读本文章。 原比赛题解仅作为个人收藏,不做任何商业用途,禁止任何人做商业用途传播。 另外,如果作者认为不妥,可以告诉我,我会马上删掉。 所有程序为个人智力成果,仅根据公式写出,未查看标准程序;此分块做法亦为个人智力成果,如需转载,请注明出处。