Luogu5285 [十二省联考2019]骗分过样例

\(case1,2,3:\)

很明显，求\(19^x\)，直接快速幂。但是\(case3\)数据很大，可以利用\(a^b \mod p= a^{b \mod (p-1)} \mod p\)边读入边取模。

\(case4:\)

没有给模数？拿第一个大数据，暴力枚举模数进行匹配，跑出来模数是\(1145141\)。

\(case5:\)

观察\(ans\)文件，这模数相当大啊！枚举显然废了。利用技巧，我们找到最相邻的\(x,y\)，满足\(x<y,19^x \mod p > 19^y \mod p\)，那么\((19^x \mod p) \times 19^{y-x}-(19^y \mod p)\)应该是\(p\)的倍数，且不会很大。

运行结果：

\[x=264708066\\ y=264708068\\ 19^x \mod p=1996649514996338529\\ 19^y \mod p=1589589654696467295\\ (19^x \mod p) \times 19^{y-x}-(19^y \mod p)=719200885258981741674 \]

这。。。炸\(long \quad long\)了，那么当然是用\(\_\_int128\)喽！

\(p\)应该是它的巨大质因数（一般模数总是质数吧），直接\(Pollard\_Rho\)

运行结果：

\[5211600617818708273 \quad 23 \quad 3 \quad 2 \]

当然就是\(5211600617818708273\)了！

\(case6,7:\)

\(wa\)。。。负数？？？

题目里好像说了自然溢出。

这样快速幂就崩了。

我也不知到它为什么有循环节。

跑一遍，循环节起点为\(55245\)，长度为\(45699\)，解决了。

\(case8:\)

\(p\)嘛，质数！

直接线性筛。

\(case9,10:\)

范围有点大，\(Miller\_Rabin\)！

卡常数，只能牺牲正确性少试验几个质数了。

\(case11:\)

\(u \rightarrow \mu\)。

线性筛！

\(case12,13:\)

这怎么算？

先把\(10^6\)以内的因子筛掉，得到一个\(\mu\)值。

那么剩下的数中，最多有两个质因数（因为必须大于\(10^6\)）。

分三种情况：

\(1.\)留下一个质数，直接\(Miller\_Rabin\)，\(\mu\)符号变向。

\(2.\)留下一个质数的平方，直接\(sqrt\)函数判断即可，\(\mu=0\)。

\(3.\)剩余的情况一定是两个大质数相乘，\(\mu\)不变。

\(case14,15,16:\)原根。