题解 P4718 【【模板】Pollard-Rho算法】

cosmicAC

2019-07-03 20:38:00

Solution

**这篇题解没有涉及到Pollard-Rho算法的任何介绍**,但是的确使用到了Pollard-Rho算法。 很多人都知道linux系统中有一个`factor`命令,支持__int128范围内的数,大概是这么用的: ``` $factor 1000000000000000034000000000000000093 1000000000000000034000000000000000093: 1000000000000000003 1000000000000000031 ``` (这个人类可以随手十字相乘分解的数字,却用了`factor`30秒) 在[Github](https://github.com/coreutils/coreutils/blob/master/src/factor.c)上有`factor`的源代码,可以看到的确使用了$\texttt{Miller-Rabin}$和$\texttt{Pollard-Rho}$算法。 但是显然我们不能直接调用`factor`,因为输出格式和此题需要的格式不符。所以可以使用`sed`工具调整输出的格式。`sed`是linux下常用的文本处理工具,语法和`ed`、`vi`等等编辑器类似。 可以发现`factor`的每一个因数之前都有一个空格,所以空格数就是因数个数。此处使用了`sed "s/[0-9:]//g"`替换掉`0..9`和`:`字符,剩下的字符串长度就是空格个数。`s`是替换命令,`s/A/B/g`的意思是把A替换成B(`g`是全部替换)。使用`${#s}`获得字符串`s`的长度。这样就可以判断数字是否是质数,空格数等于1的是质数。 然后是要输出最大的因数。由于`factor`已经帮我们排好序了,最后一个数就是最大的数。我不会使用`sed`提取最后一个数,(我会用`awk`做到可是懒得写了),于是就用`sed "s/ /\n/g"`把空格替换成了回车,然后用`tail -n1`取出最后一行。 下面是完整的脚本,可以使用`sh`运行。 ``` read a # 读入一个数,存入变量a for i in `seq 1 $a`; do # seq 1 n的意思是1到n的数 read t s=`factor $t` # ``是把其中的命令替换成命令的输出 # s存的就是factor的结果 ss=`echo $s | sed "s/[0-9:]//g"`# ss存s中空格组成的字符串 if [ ${#ss} -eq 1 ]; then # -eq表示等于 echo Prime # 输出质数 else echo $s | sed "s/ /\n/g" | tail -n1 #输出最大因数 fi done ``` 虽然洛谷上没有`sh`或者`bash`这样的语言,但是可以使用C的`system()`或者Python的`os.system()`函数提交。 最后介绍一下多行raw string的写法,这样就可以直接复制脚本了。 ```cpp R"( 多行字符串 可以带\,不会转义 )" //C++11 ``` ```python r''' 多行字符串 可以带\,不会转义 ''' #python ```