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

这篇题解没有涉及到Pollard-Rho算法的任何介绍，但是的确使用到了Pollard-Rho算法。

很多人都知道linux系统中有一个factor命令，支持__int128范围内的数，大概是这么用的：

$factor 1000000000000000034000000000000000093
1000000000000000034000000000000000093: 1000000000000000003 1000000000000000031

(这个人类可以随手十字相乘分解的数字，却用了factor30秒)

在Github上有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的写法，这样就可以直接复制脚本了。

R"(
多行字符串
可以带\，不会转义
)"              //C++11

r'''
多行字符串
可以带\，不会转义
'''             #python