LibreOJ NOI Round #1 题解

liu_cheng_ao 2017-07-06 22:16:18 2017-07-29 12:46:47

因为出现了各种偏差,笔试成绩将不计入 LNR 总成绩


笔试

答案用加粗红色字体表示。

  1. 使用 gcc 编译 C 程序时,生成调试信息的命令行选项是:
    A. -g
    B. -o
    C. -lm
    D. -s

  2. Linux 系统中具有最高权限的用户是:
    A. noilinux
    B. guest
    C. admin
    D. root

  3. 如果自己的程序在命令行/终端调用中进入死循环,哪个快捷键可以终止:
    A. Ctrl + C
    B. Ctrl + W
    C. Ctrl + Q
    D. Alt + F4

  4. NOI 评测系统中对程序源文件大小的限制是:
    A. 小于 50 KB
    B. 小于 64 KB
    C. 小于 100 KB
    D. 小于 256 KB

  5. 为程序 my.c 创建一个备份 myc.bak 时,使用的命令是:
    A. clone my.c myc.bak
    B. cp my.c myc.bak
    C. fork my.c myc.bak
    D. sudo my.c myc.bak

  6. 在考试过程中,如果出现系统死机或者崩溃现象,选手应当采取的措施是:
    A. 问旁边的人
    B. 拔掉硬盘
    C. 骂出题人毒瘤
    D. 举手示意监考人员处理

  7. NOI 比赛使用的 Linux 发行版是:
    A. NOI Linux
    B. Ubuntu
    C. Microsoft Windows
    D. RedHat

  8. 在 NOI 考试中,C++ 源文件的扩展名规定为:
    A. cc
    B. cpp
    C. c++
    D. C

  9. 水喝完了我还想喝,如何处理?
    A. 渴着
    B. 示意工作人员去卫生间,在卫生间接水喝
    C. 举手向工作人员再要一瓶
    D. 喝旁边人的

  10. 考试太简单我一个小时就 AK 了,能提前离开吗?
    A. 能
    B. 不能
    C. 看工作人员心情
    D. 选手投票表决

  11. 首届 NOI 是公元多少年举办的?
    A. 1984
    B. 1983
    C. 1926
    D. 2017

  12. NOI 比赛中提供的 C++ IDE 环境除了 GUIDE 之外,还有什么?
    A. Vim
    B. Lazarus
    C. Anjuta
    D. gedit

  13. LAN 是什么?
    A. 互联网
    B. 广域网
    C. 万维网
    D. 局域网

  14. 考试结束后选手需要:
    A. 相互讨论试题
    B. 和工作人员谈笑风生
    C. 迅速离开
    D. 找出题人讨论问题

  15. Linux 中终止后台进程 test 的命令是:
    A. close test
    B. killall test
    C. chmod 000 test
    D. del test

  16. 今年是第几届 NOI?
    A. 33
    B. 34
    C. 1
    D. 92

  17. 在 Linux 中返回上一级目录使用的命令是:
    A. cd ./
    B. cd ..
    C. cd ~
    D. cd /

  18. 当前目录中有如下文件:

 -rw-r--r-- 1 user None 8.7K Jul 2  16:35 menci  
 -rw-rw-rw- 1 user None 93   Jul 2  16:35 menci.c  
 -rwx------ 1 user None 144  Jul 2  16:35 menci.sh  

其中,可以执行的文件是:
A. menci
B. menci.c
C. menci.sh
D. 没有

  1. 如无另行说明,评测系统中对程序使用内存的限制是:
    A. 2048 MB
    B. 512 MB
    C. 以硬件资源为限
    D. 在 A 和 C 中取较小值

  2. Linux 中是否区分文件和目录名称的大小写?
    A. 是
    B. 否
    C. NOI Linux 1.4.1 版本及以前不区分,以后区分
    D. Ubuntu 不区分,NOI Linux 区分

  3. 在 Lazarus 中开始运行程序的快捷键默认是:
    A. F11
    B. F8
    C. Ctrl + R
    D. F9

  4. 提交的答案程序中如果包含 NOI 考试明确禁止使用的代码,后果是:
    A. 扣 10 分
    B. 该题 0 分
    C. 该场考试 0 分
    D. 取消比赛资格

  5. NOI 考试对 C++ 语言模板的使用有限制吗?
    A. 有
    B. 没有

  6. 在 NOI 正式考试中如何登录自己的比赛用机?
    A. 使用考前工作人员下发的账户及密码
    B. 使用 guest 帐户
    C. 使用 noilinux 帐户
    D. 使用 onilinux 帐户

  7. 测试点时间限制的含义是指:
    A. 题目允许程序从开始编译到结束运行所用时间的上限值
    B. 题目允许测评过程所用时间的上限值
    C. 题目允许程序运行所占用的用户时间总和的上限值
    D. 题目允许程序运行所占用的系统时间总和的上限值

  8. 选手在复评过程中,若因丢失密码条而向工作人员索取密码,将会怎么样?
    A. 什么也不会发生
    B. 会被取消资格
    C. 会扣 10 分
    D. 会扣 5 分

  9. 用来全面管理计算机硬件和软件资源的软件叫:
    A. BIOS
    B. 操作系统
    C. 资源管理器
    D. CCF

  10. 现代计算机所应用的存储程序原理是谁提出的?
    A. 杜子德
    B. 姚期智
    C. 艾伦·图灵
    D. 冯·诺依曼

  11. 十六进制数 233 用十进制表示是多少?
    A. 563
    B. 1063
    C. 1000110011
    D. 14221

  12. 在 NOI 考试中,Pascal 源文件的扩展名规定为:
    A. p
    B. psc
    C. fpc
    D. pas

  13. Pascal 中 integerlong integer 类型的长度和编译选项是否有关系?
    A. 没有
    B. 有

  14. 在 Anjuta 中调试程序,单步运行的快捷键默认是:
    A. F9
    B. F7
    C. F6
    D. Ctrl + S

  15. Linux 下的换行字符为:
    A. \r
    B. \r\n
    C. \n
    D. \a

  16. NOI Linux 中默认使用的 Shell 是:
    A. bash
    B. MS-DOS
    C. powershell
    D. terminate

  17. 如果 C 程序中使用了 math.h 中的函数,在编译时需要加入选项:
    A. -static
    B. -lz
    C. -lm
    D. -O2

  18. 可执行文件 a.out 从标准输入读取数据。现有一组输入数据保存在 1.in 中,使用这个测试数据文件测试自己的程序的命令是:
    A. freopen("a.in", "r", stdin)
    B. ./1.in > a.out
    C. ./1.in > a.out
    D. ./a.out < 1.in

  19. 在 Linux 系统中,将当前目录下的文件名打印到 tmp 文件中的命令是:
    A. L > tmp
    B. tmp < ls
    C. ls > tmp
    D. ls -tmp

  20. 选手在 NOI 机试过程中能否使用网络?
    A. 能
    B. 不能
    C. 看工作人员心情
    D. 选手投票表决

  21. 考试结束后,应如何处理密码条?
    A. 交给工作人员
    B. 交给领队
    C. 折成纸飞机
    D. 保存好密码条,用于复测

  22. 选手答案文件保存的目录是:
    A. 根目录
    B. home 目录
    C. 选手目录
    D. 选手目录下和考题名称相同的目录

  23. 使用高级语言编写的程序称之为:
    A. 源程序
    B. 目标程序
    C. 可执行程序
    D. 高级程序

  24. 发现鼠标或其他硬件设备有问题,选手可以:
    A. 用旁边人的
    B. 自己带一个
    C. 请工作人员更换
    D. 骂主办方

  25. 计算机直接识别和执行的语言是:
    A. 高级语言
    B. 机器语言
    C. 汇编语言
    D. 自然语言

  26. vim 编辑器中,定位到文件中第 9 行应当输入:
    A. t 9
    B. :9
    C. !9
    D. /9

  27. 使用 gcc 编译 C 程序时,生成所有警告信息的命令行选项是:
    A. -Wall
    B. -Warning
    C. -Wl
    D. -Werror

  28. 遇到下列哪些情况可以向工作人员申请加时补偿:
    A. 计算机硬件故障,并由工作人员确认和记录
    B. 考试迟到,并由工作人员确认和记录
    C. 操作系统死机,并由工作人员确认和记录
    D. 考试时去卫生间,并由工作人员确认和记录

  29. 选手进入考场不可以携带的物品是:
    A. 笔
    B. 算法教材
    C. U 盘
    D. 草稿纸

  30. NOI 竞赛组织者将在竞赛场地为选手提供的物品是:
    A. 草稿纸
    B. 女装
    C. 暖水瓶
    D. 食品

  31. NOI 比赛中选手的程序不能用的有:
    A. 使用 fork 生成进程
    B. __asm__
    C. __int128
    D. std::map

  32. NOI 比赛中,选手的哪些行为是禁止的?
    A. 在监考人员宣布 NOI 机试开始之前登陆系统
    B. 在监考人员宣布 NOI 机试开始之前触摸键盘、鼠标等外设
    C. 使用网络
    D. 在监考人员宣布 NOI 机试开始之前翻看试题

  33. 以下哪些说法是正确的?
    A. LOJ 题目排版中文引号应使用“”
    B. LOJ 题目的样例解释要用 ```plain ``` 括起来
    C. LOJ 题目中的公式和上下文之间都应空一格
    D. LOJ 上 YunoOI 的题目编号应为 2000 之后第一个空闲编号
    E. LOJ 上的头像只保存链接,你可以自己找一个图床上传然后把链接丢给 LOJ
    F. LOJ 的子任务会在出现一个错误测试点后跳过子任务其它测试点
    G. LOJ 上 Pascal 的 read(n) 读入 32 位有符号整数比 C++ 的 scanf("%d", &n) 更快
    H. ABCDEFG 选项全错


Day 1

T1. 接竹竿

By CommonAnts,题解 By CommonAnts

这是一道送分题。

其实本来 T1 是另外一道题的,然而那题因为太难被验题人合起来怼,所以就换了这道题给大家送温暖了。

算法一

哇我会枚举!暴力枚举所有可能的覆盖方案!

时间复杂度: \omega(\mathrm{poly}(n))

期望得分: 0\sim 15 分。

算法二

这不是区间 DP 裸题吗?

f(i) 表示加入第 i 张牌之后的最大得分。可得转移:

f(i)=\mathop{\max}_{j<i,c_j=c_i}(\sum_{k=j}^i v_k+\mathop{\max}_{k<j}f(k))

时间复杂度: O(n^3)

期望得分: 30 分。

算法三

用前缀最值和前缀和优化算法二。

时间复杂度: O(n^2)

期望得分: 60 分。

算法四

把算法三中前缀和(设 s_i=\sum_{j=1}^i v_j )和前缀最值(设 g_i=\mathop{\max}_{j=1}^i f_j )的式子写出来:

\begin{split} g_i & = & \max(g_{i-1},\mathop{\max}_{j<i,c_j=c_i}(s_i-s_{j-1}+g_{j-1})) \\ & = & \max(g_{i-1},s_i+\mathop{\max}_{j<i,c_j=c_i}(-s_{j-1}+g_{j-1})) \end{split}

显然后者仍然可以前缀最值优化。

h(c,i)=\mathop{\max}_{j\leq i,c_j=c} -s_{j-1}+g_{j-1} ,则:

g_i = \max(g_{i-1},s_i-h(c_i,i-1))

那么我们可以对每个 c 维护当前的 h ,由于每个位置只有一种 c ,于是每个位置要更新的 h 只有一个。

时间复杂度: O(n)

期望得分: 100 分。

v=c 的部分分是给写挂的人准备的。

如果你写了超大常数或者大常数 \log 做法你可能只能得到 75 分部分分了。

T2. 失控的未来交通工具

By CommonAnts,题解 By CommonAnts

这是一道并查集大水题。
出完这题后我做到了一道类似的题,成功成为辣鸡出题人,GG。

SYC 告诉我鏼鏼鏼在国家集训队作业里出过这个题的前半部分。Q(AQ)+

算法一

哇这性质好复杂根本搞不懂!写个记忆化搜索爽一爽吧。

每次询问设 f(i,j) 表示到 i 为止的路径是否有模 m j 的。然后记忆化搜索即可。输出时暴力模拟查询。

时间复杂度: O(cnq(n+q)) 。(因为边数也是 O(q)

期望得分: 11 分。

算法二

m=2 是一道经典大水题。连通块中如果有奇环则奇偶长度路径都存在,否则和沿任意一条路径走过去的奇偶性相同。

于是用并查集维护连通块内是否有奇环以及每个点到并查集的根路径长,输出时暴力模拟查询。

时间复杂度: O(cq+q(\alpha n+\log w))

期望得分: 21 分。结合前述算法可得 32 分。

算法三

m=2 的情况使用算法二。否则 m 是个奇质数。

如果连通块内的边模 m 全为 0,那无论怎么走都只能走出为 0 的路径。
如果有一条边模 m 不为 0,设这条边长为 w 。那么由于 m 是奇质数有 \gcd(2w,m)=1 。于是我们去那条边上绕圈就能得到模 m 为任意长的路径了。

于是用并查集维护连通块内是否有模 m 不为 0 的边即可。输出时暴力模拟查询。

时间复杂度: O(cq+q(\alpha n+\log w))

期望得分: 13 分。结合前述算法可得 45 分。

算法四

我们发现只要 m 是奇数,去一条边上绕圈就可以得到它的任意倍数了。于是我们可以得到的路径长是连通块内所有边以及 m \gcd 的倍数。

时间复杂度: O(cq+q(\alpha n+\log w))

期望得分: 7 分。结合前述算法可得 52 分。

算法五

c 很大时怎么办呢?我们观察一下这个生成器,发现它是一个等差数列。

事实上我们是要求 x,x+b,...,x+(c-1)b 中有多少个 g 的倍数。 g 的倍数每隔 \frac{g}{\gcd(b,g)} 个出现一次,于是只要求出某一次出现的位置即可。

列出方程 x+kb=0 \pmod g ,扩展欧几里得算法解之即可。

时间复杂度: O(q(\alpha n+\log w))

期望得分: 17 分。结合前述算法可得 62 分。

算法六

如果 m 不是奇数,每个方案就不再能表示成某个数的整数倍了。例如 m=4 ,1 和 2之间有一条长 1 的边,则从 1 到 2 的路径模 m 只能是 1 或 3。

不过没有关系。每个方案可以表示成某条路径加上所有环 \gcd 的若干倍。构造方法很简单:加入一个环只要从起点到环上一点来回跑 m 次,中间绕环一圈即可。

设所有边长的 \gcd g ,那么合法的解要么是 g 的倍数,要么是 2g 的倍数,要么是 g 的奇数倍。对于第三种情况只要用前两种容斥即可。

于是用并查集维护连通块内所有环的 \gcd 以及每个点到并查集的根路径长,回答询问用扩展欧几里得算法。

如何维护环的 \gcd 呢?加入连通块间的边时直接合并;加入连通块内的边 (u,v) 时,设原来环的 \gcd g u v 某路径长为 l ,新加入的边长 w ,则新的 g'=\gcd(g,2w,w+l)

时间复杂度: O(q(\alpha n+\log w))

期望得分: 100 分。

如果你用了离线轻重链剖分,Link-Cut-Tree 或者其它方式来维护路径长度的话可能会因常数过大只能得到 80 分。

T3. 动态几何问题

By xumingkuan,题解 By xumingkuan

这是一道和几何无关的数论题。

让我们先来把几何部分搞定吧。由于 KX=\sqrt{a}, YL=\sqrt{b}, XY=1 ,且 KX \perp XY, XY \perp YL ,根据勾股定理,有 S_{KLCD} = {KL}^2 = \left(\sqrt{a} + \sqrt{b}\right)^2 + 1^2 = a + b + 1 + 2\sqrt{ab} 。于是, S_{KLCD} 为整数等价于 ab 为完全平方数。

(咦,这好像是Topcoder原题……不对,这数据范围什么鬼啊……这题真的可做吗?)

算法一

N=1 时,这题就是在问不超过 M 的完全平方数有多少个,直接输出 \lfloor \sqrt{M} \rfloor 就好啦。

期望得分: 3 分。

算法二

哇我会写for循环!枚举所有有序数对 (a,b) ,判断是不是完全平方数即可。

时间复杂度: O(NM)

期望得分: 5 分。结合上述算法可得 8 分。

算法三

我们可以将 a b 中的所有平方因子除去以后所得的数分别记为 d d' (即:将 a 分解质因数,设 a = p_1^{2k_1+1} \times p_2^{2k_2+1} \times ... \times q_1^{2w_1} \times q_2^{2w_2} (其中 p_i, q_i 是质数, k_i 是非负整数, w_i 是正整数),令 d = p_1 \times p_2 \times ... ;由 b 计算 d' 的方法类似)。那么因为 ab 是完全平方数,所以 dd' 也是完全平方数。于是对于任意质数 p | d ,有 p^2 | dd' ,又因 d d' 都没有平方因子,所以 p^2 不整除 d ,于是 p | d' 。所以 d | d' 。同理, d' | d 于是有 d = d'

我们可以枚举 a ,由于 a / d a 的约数中最大的完全平方数,我们可以通过枚举不超过 a 的所有完全平方数看是不是 a 的约数(当然直接把 a 分解质因数也行)来计算出 d ,那么 b 一定是 d 的完全平方数倍,枚举这个倍数,这样就能找出所有有序数对 (a, b) 了。当然其实并不用枚举——显然 a, d 固定时有序数对 (a, b) 一共有 \lfloor \sqrt{M / d} \rfloor 个。

时间复杂度: O(N \cdot (\sqrt{N} + \sqrt{M})) O(N \cdot \sqrt{N})

期望得分: 15 ~ 18 分。

算法四

换一种思路,考虑枚举 d ,计算有多少组对应的有序数对 (a, b) 。如果我们枚举了 d (注意 d 只能取不包含平方因子的数),那么只需让 a / d, b / d 为完全平方数,并且 1 \leq a \leq N, 1 \leq b \leq M 即可满足要求。当 d 确定时, A, B 可以取的值的数量分别与不超过 \lfloor N / d \rfloor \lfloor M / d \rfloor 的完全平方数个数相同,即分别为 \big\lfloor\sqrt{\lfloor N / d \rfloor}\big\rfloor \big\lfloor\sqrt{\lfloor M / d \rfloor}\big\rfloor

现在的问题就变成了找出所有 d ,即不超过 \min(N, M) 的所有不包含平方因子的数。我们可以用筛法求出来,即把所有(大于 1 的)完全平方数的倍数筛掉,剩下的就是不包含平方因子的数。这样做的时间复杂度是 \min(N, M) \times \sum_{i = 1}^{\lfloor \sqrt{ \min(N, M)} \rfloor}{i^{-2}} = O( \min(N, M)) 。然后枚举 d ,将对应的 a b 的数量乘起来(即 \big\lfloor\sqrt{\lfloor N / d \rfloor}\big\rfloor \times \big\lfloor\sqrt{\lfloor M / d \rfloor}\big\rfloor )计入答案即可。

时间复杂度: O(\min(N, M))

期望得分: 30 分。

算法五

根据算法四,答案 =\sum_{x=1}^{\min(N, M)} \mu^2(x) \cdot \big\lfloor\sqrt{\lfloor N / x \rfloor}\big\rfloor \cdot \big\lfloor\sqrt{\lfloor M / x \rfloor}\big\rfloor

哇我会杜教筛!

注意到根据容斥原理, \mu^2 的前缀和 \sum_{x=1}^{n} \mu^2(x) = \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \mu(i) \cdot \lfloor \frac{n}{i^2} \rfloor 可以在 O(\sqrt{n}) 的时间复杂度内计算,而 \big\lfloor\sqrt{\lfloor N / x \rfloor}\big\rfloor \cdot \big\lfloor\sqrt{\lfloor M / x \rfloor}\big\rfloor 的取值个数又不是很多,所以可以考虑对于 \big\lfloor\sqrt{\lfloor N / x \rfloor}\big\rfloor \cdot \big\lfloor\sqrt{\lfloor M / x \rfloor}\big\rfloor 的每种取值计算对应的一段 \mu^2 的区间和。

(下面几个算法中,为了方便描述,不妨设 N \leq M ;另外,这篇题解中的 N 指的是原题中的 N (或 N,M 中的较小值),而 n 是一个普通的变量)

我们可以用线性筛预处理 \sqrt{N} 以内的所有 \mu 的值( \mu(1), \mu(2), \dots, \mu(\lfloor{\sqrt{N}\rfloor}) )。

x 1 N 的过程中, \big\lfloor\sqrt{\lfloor N / x \rfloor}\big\rfloor 一共改变了 O(N^{1/3}) 次值, \big\lfloor\sqrt{\lfloor M / x \rfloor}\big\rfloor 一共改变了 O(\min(M^{1/3}, N)) 次值,所以 \big\lfloor\sqrt{\lfloor N / x \rfloor}\big\rfloor \cdot \big\lfloor\sqrt{\lfloor M / x \rfloor}\big\rfloor 一共改变了 O(\min(M^{1/3}, N)) 次值,这也就是我们需要计算 \mu^2 的前缀和的次数。这时我们发现,如果直接将计算 \mu^2 的前缀和的复杂度看做 O(\sqrt{N}) ,这个算法的时间复杂度约为 O(N^{1/2} \cdot M^{1/3}) ,并不是很优秀,所以需要仔细分析一下时间复杂度。

首先我们需要对 n=1? ~ \min(M^{1/3}, N)? 计算 \sum_{x=1}^{n} \mu^2(x)? ,这部分的时间复杂度为 O\left(\int_1^{\min(M^{1/3},N)} \sqrt{x} \mathrm{d}x\right) = O\left(\min(M^{1/2}, N^{3/2})\right)?

然后我们需要对 \sqrt{M / n} = \sqrt{M / N} ~ M^{1/3} 计算 \sum_{x=1}^{n} \mu^2(x) ,这部分的时间复杂度为 O\left(\int_{\sqrt{M/N}}^{M^{1/3}} \frac{\sqrt{M}}{x} \mathrm{d}x\right) = O\left(\sqrt{M}(\frac{1}{2}\log{N} - \frac{1}{6}\log{M})\right)

所以,当 \max(N,M) > \left(\min(N,M)\right)^3 时,时间复杂度为 O\left(\left(\min(N,M)\right)^{1.5}\right) ;否则,时间复杂度为 O\left(\left(\max(N,M)\right)^{0.5} \log{\min(N,M)}\right) 。更直观地,当 N=M 时,时间复杂度为 O(N^{0.5} \log N)

期望得分: 60 ~ 78 分。

算法五(二)

感谢 fstqwq 提供此解法。

我们换一种思路,考虑枚举数对 (a, b) 的最大公约数,设为 d 。显然, \frac a d \frac b d 必须是互质的完全平方数,于是我们可以统计 [1, \lfloor \sqrt{\frac N d} \rfloor] [1, \lfloor \sqrt{\frac M d} \rfloor] 中互质数的对数。

于是答案变成了 \sum _d \sum _i ^ {\lfloor \sqrt{\frac N d} \rfloor} \sum _j ^ {\lfloor \sqrt{\frac M d} \rfloor} [\gcd (i, j) = 1] 。后半部分是一个经典的莫比乌斯反演问题;于是我们在对 \sqrt{N} 进行线性筛后就可以对 d 分块处理后,再分块处理进行计算了。

时间复杂度 \int _1 ^ {N ^ {1 / 2}} (\sqrt N / x) ^ {1 / 2} dx = O(\sqrt N) ,但是常数过大得分不明。

期望得分: 60 \sim 95 分。

算法六

如果预处理了 \sqrt{n} 以内的 \mu 的前缀和, \mu^2 的前缀和就能在 O(n^{1/3}) 而不是 O(\sqrt{n}) 的时间内计算,因为 \lfloor \frac{n}{i^2} \rfloor 一共只有不超过 O(n^{1/3}) 种取值(因为要么 i \leq n^{1/3} ,要么 \lfloor \frac{n}{i^2} \rfloor \leq n^{1/3} )。同时我们也可以顺便预处理一下 \mu^2 的前缀和。

假设我们用线性筛预处理了 S 以内( S \ge \sqrt{N} )的 \mu \mu^2 的前缀和,同样使用积分来分析一下时间复杂度:

首先如果 S<\min(M^{1/3},N) ,我们需要对 n=S ~ \min(M^{1/3}, N) 计算 \sum_{x=1}^{n} \mu^2(x) ,这部分的时间复杂度为 O\left(\int_S^{\min(M^{1/3},N)} x^{1/3} \mathrm{d}x\right) = O\left(\min(M^{4/9},N^{4/3}) - S^{4/3}\right)

然后我们需要对 \sqrt{M / n} = \sqrt{M / N} ~ \min(M^{1/3},\sqrt{M/S}) 计算 \sum_{x=1}^{n} \mu^2(x) ,这部分的时间复杂度为 O\left(\int_{\sqrt{M/N}}^{\min(M^{1/3},\sqrt{M/S})} M^{1/3}x^{-2/3} \mathrm{d}x\right) = O\left(\min(M^{4/9},M^{1/2}S^{-1/6}) - M^{1/2}N^{-1/6}\right)

所以总时间复杂度是 O(S + \min(M^{4/9}, N^{4/3} \cdot [S<\min(M^{1/3},N)] + M^{1/2}S^{-1/6} \cdot [S<N]))

所以,当 \max(N,M) > \left(\min(N,M)\right)^{7/3} 时,取 S=\min(N,M) 可得时间复杂度 O(\min(N,M)) ;否则,当 \max(N,M) > \left(\min(N,M)\right)^{7/6} 时,取 S = \left(\max(N,M)\right)^{3/7} 可得时间复杂度 O\left( \left(\max(N,M)\right)^{3/7}\right) ;否则,取 S = \sqrt{\min(N,M)} 可得时间复杂度 O\left(\sqrt{\min(N,M)}\right) 。更直观地,当 N=M 时,时间复杂度为 O(\sqrt{N})

期望得分: 95 分。如果使用了一些奇技淫巧有可能拿到 100 分。

算法七

算法六中当 \max(N,M) \le \left(\min(N,M)\right)^{7/6} 时,时间复杂度瓶颈为 O(\sqrt{N}) 的线性筛。如果令线性筛预处理范围 S < \sqrt{N} 会怎么样呢?

首先我们有算法六的全部计算过程,这部分的复杂度为 O(S + \min(M^{4/9}, N^{4/3} \cdot [S<M^{1/3}] + M^{1/2}S^{-1/6}))

为了方便描述,下面记 \sum\mu(n) = \sum_{x=1}^{n} \mu(x), \sum\mu^2(n) = \sum_{x=1}^{n} \mu^2(x)

与算法六不同的是,我们不能在 O(\sqrt{n}) 的时间复杂度内计算一些 \mu^2 的前缀和了。具体地说,我们需要计算这些 \mu^2 的前缀和: \sum\mu^2(N), \sum\mu^2\left(\left\lfloor \frac{M}{\left(\lfloor\sqrt{M / N}\rfloor + 1\right)^2} \right\rfloor\right), \sum\mu^2\left(\left\lfloor \frac{M}{\left(\lfloor\sqrt{M / N}\rfloor + 2\right)^2} \right\rfloor\right), \dots (也需要计算一些形如 \sum\mu^2(\lfloor \frac{N}{\dots} \rfloor) 的前缀和,但是计算它们的时间不会超过计算形如 \sum\mu^2(\lfloor \frac{M}{\dots} \rfloor) 的时间,故无需再考虑)

再看计算 \mu^2 的前缀和的过程: \sum\mu^2(n) = \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \mu(i) \cdot \lfloor \frac{n}{i^2} \rfloor 。在计算 \sum\mu^2(n) 时,我们需要求 \sum\mu(\lfloor \sqrt{n} \rfloor), \sum\mu(\lfloor \sqrt{n / 2} \rfloor), \sum\mu(\lfloor \sqrt{n / 3} \rfloor), \dots

再看计算 \mu 的前缀和的过程: \sum\mu(n) = 1 - \sum_{i=2}^{n} \sum\mu(\lfloor n / i \rfloor) 。我们可以一次性求出所有满足 \lfloor n / i \rfloor > S \sum\mu(\lfloor n / i \rfloor) i 为正整数),所需时间复杂度为 O\left(\int_{1}^{n / S} \sqrt{n / x} \mathrm{d}x\right) = O(n \cdot S^{-1/2}) (题外话:杜教筛 O(n^{2/3}) 的时间复杂度就是 O(n \cdot S^{-1/2} + S) 的最小值)。

根据上述信息,我们可以列出来所有需要计算的 \mu 的前缀和:

\mathrm{for}_{i=\lfloor \sqrt{M/N} \rfloor}^{\lfloor \sqrt{M}/S \rfloor} \mathrm{for}_{j=1}^{\lfloor M / (i^2S^2) \rfloor} \sum\mu(\lfloor \frac{\sqrt{M}}{i \sqrt{j}}\rfloor)