1 Miller-Rabin
1.1 朴素筛法
- 如何判断一个数是不是质数？
- 如果 (2,3,cdots,lfloorsqrt n floor ot|~n)，那么 (n) 就是质数。
- 算法复杂度 (O(sqrt n))，有点慢。
可惜，如果要保证答案正确，似乎并没有什么好方法了……
等等，答案正确？
1.2 引入&铺垫
- 没错，我们要使用不正确的算法过题了。
1.2.1 为什么“不正确”的算法能过题
- 如果你想在机房颓废，但是不知道老师在不在，你可以使用以下这个策略：
- 颓一分钟，有 (0.8) 的概率被老师发现。
- 重复第 (1) 步 (10) 次。
- 如果都没被老师发现，就认为老师不在。
这样的话，我们唯一的失误就是老师在，你颓废 (10) 次没被发现。
这个的概率是多少呢？(0.2^{10}=0.0000001024)。但是如果你只重复一次，失败的概率高达 (0.2)。
这说明了什么？
我们只要用一个正确率相对高的方法随机采样判断，失误概率可以指数级下降。
1.2.2 一些前置知识
- 这些知识你可能小学就学过了，但是不要紧，我们来复习一下。下文中 (p) 都是素数。
- 如果 ((a,p)=1)，(a^{p-1}equiv1pmod p)
- 如果 (x^2equiv1pmod p)，则 (xequivpm1pmod p)。
我并不知道为什么很多人说第二个公式 (p) 必须是奇素数，(2) 应该也可以吧
1.3 正片开始
- 我们先钦定一个质数 (p)。你可以随便钦定，比如 (2)，(3)，(13)，甚至是 (19260817)。
- Case 1：显然如果我们判断的数 (x=p)，那么 (x) 是素数。
- Case 2：显然如果 (p|x) 且 (x>p)，那么 (x) 是合数。
- Case 3：显然如果 (p^{x-1} otequiv1pmod x)，那么 (x) 是合数。
- Case 4：以上三种都没有满足。
- 初始化 (k=x-1)。
- 如果 (k) 是奇数，我们就认定 (x) 是素数（没错就这么草率）。
- (k=frac{k}{2},t=p^k\%x)。
- 如果 (t otequivpm1pmod x)，我们就知道 (x) 不是素数了。
- 如果 (tequiv-1pmod x)，我们就认定 (x) 是素数（没错就这么草率）。
- 回到第一步。
注意到在判断 (x) 不是素数的时候，我们是肯定的，但是在返回 (x) 是素数的时候，我用上了草率两字。不难举出很多判断是素数时的反例，然而大多数情况下，判断还是相对准确的。
因此结合 1.2.1 中的内容，只要我们多判断几次，正确率就能接近百分之百了。
注意到我们并没有限制 (p)，所以 (p) 可以任意取正整数。由于题解中都这么写，我推荐大家使用 (2,3,5,7,11,13,19,61,2333,24251) 这十个数，听说它能顺利判断出所有 long long 范围的质数。
1.4 实现
1.4.1 小坑点
由于模数 (x) 在 long long 范围，两个模 (x) 意义下的非负整数相乘可能超出 long long 范围，由于 __int128 效率十分感人并且并不能在 NOI 系列比赛中使用，笔者采用龟速乘实现 (a imes b\%c)。
1.4.2 代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+(ch&15),ch=getchar();
return s;
}
int mul(int x,int y,int p)
{
int res=0;
for(int now=x; y; y>>=1,now<<=1,now%=p) (y&1)&&(res+=now,res%=p);
return res;
}
int qp(int x,int y,int p)
{
int res=1;
for(int now=x; y; y>>=1,now=mul(now,now,p)) (y&1)&&(res=mul(res,now,p));
return res;
}
bool Miller_Rabin(int x,int p)
{
for(int t,k=x-1; !(k&1);)
{
k>>=1,t=qp(p,k,x);
if(t!=1&&t!=x-1) return 0;
if(t==x-1) return 1;
}
return 1;
}
const int P[10]={2,3,5,7,11,13,19,61,2333,24251};
bool is_prime(int x)
{
for(int i=0; i<10; ++i)
{
if(x==P[i]) return 1;
if(x%P[i]==0) return 0;
if(qp(P[i]%x,x-1,x)!=1) return 0;
if(!Miller_Rabin(x,P[i]%x)) return 0;
}
return 1;
}
signed main()
{
int n=read();
if(is_prime(n)) puts("114514");
else puts("1919810");
return 0;
}
2 Pollard-Rho
2.1 朴素筛法
- 如何分解质因数？
- 找出 (x) 的所有因子：对所有小于 (sqrt n) 的质数试除。
- 算法复杂度 (O(sqrt n))，有点慢。
可惜，如果要保证算法靠谱，似乎并没有什么好方法了……
等等，算法靠谱？
2.2 跳过op
小手一抖，op 没有，我们直入正题。
2.2.1 从 MR 到 PR
我们已经会高效判断 (x) 是不是质数了。
如果我们要分解 (x)，并且知道 (x) 不是质数，我们必然知道 (x) 有至少一个不超过 (sqrt x) 的质因子。
如果我们已经找到了一个数 (t(t>1)) 使得 (t|x)，我们就可以递归处理 (t) 和 (frac{x}{t}) 了。但是 (t) 并不好找。
这时，一个神仙出现了：找不到 (t)，我们就找 (t) 的倍数，这样就增加了 (sqrt x) 倍的获奖概率！（为什么是 (sqrt x) 倍的中奖概率呢，因为必然存在一个 (t<sqrt x)，而 (t) 的整数倍在 (x) 以内至少存在 (frac{x}{t}geqsqrt x) 个）
如果我们每次尝试成功的概率是 (sqrt x)，据说期望复杂度就是 ( ext O(n^frac{1}{4}))
但是找到 (t) 的倍数又怎么转化回 (t) 呢……没错，就是 (gcd)！
因此我们只要随便选几个数 (gcd) 就行了。
2.2.2 神奇的优化
- 神奇的随机算法，floyd 判圈。
- gcd 优化。
- 一个我也看不懂的神奇优化，见讨论区。
2.3 代码（被卡常）
由于太逊就不给了。
2.4 悲报
我不懂为什么别人这么快啊……最后还是 system 过了这题/ll