链接

https://ac.nowcoder.com/acm/contest/15789

B Basic Gcd Problem

题意

定义
$$
f_c(x)=
\begin{cases}
max_{i=1}^n c\cdot f_c(\gcd(i,x)) &x\gt1\
1&x=1
\end{cases}
$$

输入c和x

题解

f函数迭代次数越多，则值越大，也就是x取gcd的次数越多越好，所以每次选择x的最大因子即可。最终使用快速幂解决。

C Count New String

题意

给你一个字符串S，定义f(s,x,y)是一个字符串，长度为y-x+1，他的第k个字符串为$max_{i=x,x+1…x+k}S_i$

你要计算$A=\lbrace f(f(s,x_1,y_1),x_2-x_1+1,y_2-x_1+1)| 1\le x_1\le x_2 \le y_2 \le y_1\le n \rbrace$

题解

对于第一层而言，只需要考虑所有后缀即可。于是成了给你n个后缀，你需要计算这些后缀的本质不同的子串，由于后缀间的最长公共后缀很长，所以在后缀自动机上要记录每个后缀对应的last结点。从那个地方开始拓展即可。

F Finding the Order

题意

有两条平行线，一条上有AB两个点，另一条有CD两个点。

问你是AB与CD同向，还是AB与DC同向。

题解

考虑梯形ABCD，有$AC+BD>AD+BC$

考虑梯形ABDC，有$AD+BC>AC+BD$

H Harder Gcd Problem

题目描述

给你1到n这n个数，每个数只能用一次，你要选出m个数对，数对的两个数两两互素，问你最多选多少个数对。

数据范围

$n<2\times10^5$

题解

从大到小考虑奇素数p，取出他的所有倍数，可以证明，如果至少有两个，则一定有$p$和$2p$, 如果有奇数个，则拿出2p，然后两两配对，如果有偶数个，则两两配对。

最后剩下来的一定全是偶数和一个1，直接两两配对即可。