分解质因数 - OI Wiki
文章推薦指數： 80 %
我们希望有方法来优化猜测。
朴素算法与Pollard Rho 算法引入. 最简单的算法即为从 ...
跳转至简介比赛相关工具软件语言基础算法基础搜索动态规划字符串数学数据结构图论计算几何杂项专题关于HuluschoolOIWikiOI-wiki/OI-wiki简介简介GettingStarted关于本项目如何参与格式手册F.A.Q.用Docker部署OIWiki镜像站列表致谢比赛相关比赛相关比赛相关简介赛事赛事OI赛事与赛制ICPC/CCPC赛事与赛制题型题型题型概述交互题学习路线学习资源技巧技巧读入、输出优化常见错误常见技巧出题工具软件工具软件工具软件简介代码编辑工具代码编辑工具VimEmacsVSCodeAtomEclipseNotepad++KateDev-C++GeanyXcodeGUIDESublimeText评测工具评测工具评测工具简介ArbiterCenaCCRPlusLemon命令行WSL(Windows10)SpecialJudgeTestlibTestlibTestlib简介通用GeneratorValidatorInteractorCheckerPolygonOJ工具LaTeX入门Git语言基础语言基础语言基础简介C++基础C++基础Hello,World!C++语法基础变量运算流程控制语句流程控制语句分支循环高级数据类型高级数据类型数组结构体指针函数文件操作C++标准库C++标准库C++标准库简介STL容器STL容器STL容器简介迭代器序列式容器关联式容器无序关联式容器容器适配器STL算法bitsetstringpairC++进阶C++进阶类命名空间值类别重载运算符引用常值新版C++特性Lambda表达式pb_dspb_dspb_ds简介堆平衡树C++与其他常用语言的区别Pascal转C++急救Python速成Java速成算法基础算法基础算法基础简介复杂度枚举模拟递归&分治贪心排序排序排序简介选择排序冒泡排序插入排序计数排序基数排序快速排序归并排序堆排序桶排序希尔排序锦标赛排序排序相关STL排序应用前缀和&差分二分倍增构造搜索搜索搜索部分简介DFS（搜索）BFS（搜索）双向搜索启发式搜索A*迭代加深搜索IDA*回溯法DancingLinksAlpha-Beta剪枝优化动态规划动态规划动态规划部分简介动态规划基础记忆化搜索背包DP区间DPDAG上的DP树形DP状压DP数位DP插头DP计数DP动态DP概率DPDP优化DP优化单调队列/单调栈优化斜率优化四边形不等式优化状态设计优化其它DP方法字符串字符串字符串部分简介字符串基础标准库字符串匹配字符串哈希字典树(Trie)前缀函数与KMP算法Boyer-Moore算法Z函数（扩展KMP）自动机AC自动机后缀数组(SA)后缀数组(SA)后缀数组简介最优原地后缀排序算法后缀自动机(SAM)后缀平衡树广义后缀自动机后缀树Manacher回文树序列自动机最小表示法Lyndon分解Main-Lorentz算法数学数学数学部分简介符号复数位运算快速幂进位制高精度计算平衡三进制数论数论数论基础素数最大公约数数论分块欧拉函数筛法Meissel-Lehmer算法分解质因数分解质因数目录问题引入朴素算法与PollardRho算法引入生日悖论构造伪随机函数优化随机算法时间复杂度分析Floyd判环倍增优化评论裴蜀定理类欧几里德算法欧拉定理&费马小定理乘法逆元线性同余方程中国剩余定理威尔逊定理升幂定理卢卡斯定理二次剩余拉格朗日定理原根BSGS莫比乌斯反演杜教筛PowerfulNumber筛Min_25筛洲阁筛二次域连分数Stern-Brocot树与Farey序列Pell方程多项式与生成函数多项式与生成函数简介代数基本定理拉格朗日插值快速傅里叶变换快速数论变换快速复数论变换快速沃尔什变换ChirpZ变换多项式求逆多项式开方多项式除法|取模多项式对数函数|指数函数多项式牛顿迭代多项式多点求值|快速插值多项式三角函数多项式反三角函数常系数齐次线性递推多项式平移|连续点值平移符号化方法普通生成函数指数生成函数狄利克雷生成函数线性代数线性代数线性代数简介向量矩阵高斯消元特征多项式线性基线性规划线性规划线性规划简介单纯形算法组合数学组合数学排列组合卡特兰数斯特林数贝尔数伯努利数康托展开容斥原理抽屉原理EulerianNumber分拆数群论群论群论简介置换群概率论概率论快速上手基本概念条件概率与独立性随机变量随机变量的数字特征斐波那契数列博弈论博弈论博弈论简介公平组合游戏非公平组合游戏反常游戏牛顿迭代法数值积分分段打表傅里叶-莫茨金消元法序理论杨氏矩阵Schreier–Sims算法Berlekamp-Massey算法数据结构数据结构数据结构部分简介栈队列链表哈希表并查集并查集并查集并查集复杂度堆堆堆简介二叉堆配对堆左偏树块状数据结构块状数据结构分块思想块状数组块状链表树分块SqrtTree单调栈单调队列ST表树状数组线段树李超线段树区间最值操作&区间历史最值划分树二叉搜索树&平衡树二叉搜索树&平衡树二叉搜索树简介TreapSplayWBLTSizeBalancedTreeAVL树替罪羊树笛卡尔树红黑树左偏红黑树跳表可持久化数据结构可持久化数据结构可持久化数据结构简介可持久化线段树可持久化块状数组可持久化平衡树可持久化字典树可持久化可并堆树套树树套树线段树套线段树平衡树套线段树线段树套平衡树树状数组套主席树分块套树状数组K-DTree珂朵莉树动态树动态树LinkCutTreeEulerTourTreeTopTree析合树PQ树手指树霍夫曼树图论图论图论部分简介图论相关概念图的存储DFS（图论）BFS（图论）树上问题树上问题树基础树的直径最近公共祖先树的重心树链剖分树上启发式合并虚树树分治动态树分治AHU算法树哈希矩阵树定理有向无环图拓扑排序最小生成树斯坦纳树最小树形图最小直径生成树最短路拆点差分约束k短路同余最短路连通性相关连通性相关强连通分量双连通分量割点和桥圆方树2-SAT欧拉图哈密顿图二分图最小环平面图图的着色网络流网络流网络流简介最大流最小割费用流上下界网络流Stoer-Wagner算法图的匹配图的匹配图匹配增广路二分图最大匹配二分图最大权匹配一般图最大匹配一般图最大权匹配Prufer序列LGV引理弦图计算几何计算几何计算几何部分简介二维计算几何基础三维计算几何基础极坐标系距离Pick定理三角剖分凸包扫描线旋转卡壳半平面交平面最近点对随机增量法反演变换计算几何杂项杂项杂项杂项简介离散化双指针离线算法离线算法离线算法简介CDQ分治整体二分莫队算法莫队算法莫队算法简介普通莫队算法带修改莫队树上莫队回滚莫队莫队配合bitset分数规划随机化随机化随机函数随机化技巧爬山算法模拟退火悬线法计算理论基础字节顺序约瑟夫问题格雷码表达式求值在一台机器上规划任务主元素问题Garsia-Wachs算法15-puzzleKahan求和专题专题RMQ并查集应用括号序列关于Hulu关于Hulu关于Hulu目录问题引入朴素算法与PollardRho算法引入生日悖论构造伪随机函数优化随机算法时间复杂度分析Floyd判环倍增优化评论分解质因数问题引入给定一个正整数，试快速找到它的一个因数。
考虑朴素算法，因数是成对分布的，的所有因数可以被分成两块，即和。
只需要把里的数遍历一遍，再根据除法就可以找出至少两个因数了。
这个方法的时间复杂度为。
当时，这个算法的运行时间我们是无法接受的，希望有更优秀的算法。
一种想法是通过随机的方法，猜测一个数是不是的因数，如果运气好可以在的时间复杂度下求解答案，但是对于的数据，成功猜测的概率是,期望猜测的次数是。
如果是在里进行猜测，成功率会大一些。
我们希望有方法来优化猜测。
朴素算法与PollardRho算法引入最简单的算法即为从进行遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14//C++Version
list
while(N%i==0)N/=i;
result.push_back(i);
}
}
if(N!=1){//说明再经过操作之后N留下了一个素数
result.push_back(N);
}
returnresult;
}
1
2
3
4
5
6
7
8
9
10
11#PythonVersion
defbreakdown(N):
result=[]
foriinrange(2,int(sqrt(N))+1):
ifN%i==0:#如果i能够整除N，说明i为N的一个质因子。
whileN%i==0:
N=N//i
result.append(i)
ifN!=1:#说明再经过操作之后N留下了一个素数
result.append(N)
returnresult
我们能够证明result中的所有元素均为N的素因数。
证明result中均为的素因数首先证明元素均为的素因数：因为当且仅当N%i==0满足时，result发生变化：储存，说明此时能整除，说明了存在一个数使得，即（其中，为自身发生变化后遇到时所除的数。
我们注意到result若在push之前就已经有数了，为，那么有N，被除的乘积即为）。
所以为的因子。
其次证明result中均为素数。
我们假设存在一个在result中的合数，并根据整数基本定理，分解为一个素数序列，而因为，所以它一定会在之前被遍历到，并令while(N%k1==0)N/=k1，即让N没有了素因子，故遍历到时，N和已经没有了整除关系了。
值得指出的是，如果开始已经打了一个素数表的话，时间复杂度将从下降到。
去筛法处查阅更多打表的信息。
例题：CF1445C而下面复杂度复杂度更低的Pollard-Rho算法是一种用于快速分解非平凡因数的算法（注意！非平凡因子不是素因子）。
而在此之前需要先引入生日悖论。
生日悖论不考虑出生年份，问：一个房间中至少多少人，才能使其中两个人生日相同的概率达到?解：假设一年有天，房间中有人，用整数对这些人进行编号。
假定每个人的生日均匀分布于天之中，且两个人的生日相互独立。
设k个人生日互不相同为事件,则事件的概率为至少有两个人生日相同的概率为。
根据题意可知,那么就有由不等式可得然而我们可以得到一个不等式方程，，其中是一个概率。
将代入，解得。
所以一个房间中至少23人，使其中两个人生日相同的概率达到,但这个数学事实十分反直觉，故称之为一个悖论。
当，时，出现两个人同一天生日的概率将大于。
那么在一年有天的情况下，当房间中有个人时，至少有两个人的生日相同的概率约为。
考虑一个问题，设置一个数据，在里随机选取个数（时就是它自己），使它们之间有两个数的差值为。
当时成功的概率是，当时成功的概率是（考虑绝对值，可以取或），随着的增大，这个概率也会增大最后趋向于1。
构造伪随机函数我们通过来生成一个随机数序列，其中，是一个随机的常数。
随机取一个，令，在一定范围内可以认为这个数列是“随机”的。
举个例子，设生成的数据为可以发现数据在3以后都在11,23,31之间循环，这也是被称为伪随机函数的原因。
如果将这些数如下图一样排列起来，会发现这个图像酷似一个，算法也因此得名rho。
优化随机算法最大公约数一定是某个数的约数，即，只要选适当的使得，就可以求得一个约数。
满足这样条件的不少，有若干个质因子，每个质因子及其倍数都是可行的。
将生日悖论应用到随机算法中，伪随机数序列中不同值的数量约为个。
设为的最小非平凡因子，显然有。
记，推导可得：于是就得到了一个新序列（当然也可以写作)，并且根据生日悖论可以得知序列中不同值的个数约为。
假设存在两个位置，使得，这意味着,因此我们可以通过获得的一个非平凡因子。
时间复杂度分析我们期望枚举个来分解出的一个非平凡因子，因此。
Pollard-rho算法能够在的期望时间复杂度内分解出的一个非平凡因子，通过上面的分析可知，那么Pollard-rho算法的总时间复杂度为。
下面介绍两种实现算法，两种算法都可以在的时间复杂度内完成。
Floyd判环假设两个人在赛跑，A的速度快，B的速度慢，经过一定时间后，A一定会和B相遇，且相遇时A跑过的总距离减去B跑过的总距离一定是圈长的n倍。
设，每一次更新，只要检查在更新过程中a、b是否相等，如果相等了，那么就出现了环。
我们每次令，判断d是否满足，若满足则可直接返回。
由于是一个伪随机数列，必定会形成环，在形成环时就不能再继续操作了，直接返回n本身，并且在后续操作里调整随机常数，重新分解。
基于Floyd判环的Pollard-Rho算法1
2
3
4
5
6
7
8
9
10
11
12
13//C++Version
llPollard_Rho(llN){
llc=rand()%(N-1)+1;
llt=f(0,c,N);
llr=f(f(0,c,N),c,N);
while(t!=r){
lld=gcd(abs(t-r),N);
if(d>1)returnd;
t=f(t,c,N);
r=f(f(r,c,N),c,N);
}
returnN;
}
1
2
3
4
5
6
7
8
9
10
11
12#PythonVersion
defPollard_Rho(N):
c=random.randint(0,32767)%(N-1)+1
t=f(0,c,N)
r=f(f(0,c,N),c,N)
whilet!=r:
d=gcd(abs(t-r),N)
ifd>1:
returnd
t=f(t,c,N)
r=f(f(r,c,N),c,N)
returnN
倍增优化使用求解的时间复杂度为，频繁地调用会使算法运行地很慢，可以通过乘法累积来减少求的次数。
如果，则有，，并且有。
我们每过一段时间将这些差值进行运算，设，如果某一时刻得到那么表示分解失败，退出并返回本身。
每隔个数，计算是否满足。
此处取，可以根据实际情况进行调节。
参考实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18llPollard_Rho(llx){
lls=0,t=0;
llc=rand()%(x-1)+1;
intstep=0,goal=1;
llval=1;
for(goal=1;;goal<<=1,s=t,val=1){
for(step=1;step<=goal;++step){
t=f(t,c,x);
val=val*abs(t-s)%x;
if((step%127)==0){
lld=gcd(val,x);
if(d>1)returnd;
}
}
lld=gcd(val,x);
if(d>1)returnd;
}
}
例题：P4718【模板】Pollard-Rho算法对于一个数，用MillerRabin算法判断是否为素数，如果是就可以直接返回了，否则用Pollard-Rho算法找一个因子，将除去因子。
再递归分解和，用MillerRabin判断是否出现质因子，并用max_factor更新就可以求出最大质因子了。
由于这个题目的数据过于庞大，用Floyd判环的方法是不够的，这里采用倍增优化的方法。
参考实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88#include<bits/stdc++.h>
usingnamespacestd;
typedeflonglongll;
intt;
longlongmax_factor,n;
longlonggcd(longlonga,longlongb){
if(b==0)returna;
returngcd(b,a%b);
}
longlongquick_pow(longlongx,longlongp,longlongmod){//快速幂
longlongans=1;
while(p){
if(p&1)ans=(__int128)ans*x%mod;
x=(__int128)x*x%mod;
p>>=1;
}
returnans;
}
boolMiller_Rabin(longlongp){//判断素数
if(p<2)return0;
if(p==2)return1;
if(p==3)return1;
longlongd=p-1,r=0;
while(!(d&1))++r,d>>=1;//将d处理为奇数
for(longlongk=0;k<10;++k){
longlonga=rand()%(p-2)+2;
longlongx=quick_pow(a,d,p);
if(x==1||x==p-1)continue;
for(inti=0;i
延伸文章資訊
- 1整数分解- 维基百科，自由的百科全书
在數學中，整數分解（英語：integer factorization）又稱質因數分解（prime factorization），是將一個正整數寫成幾個因數的乘積。例如，給出45這個數，它可以分解...
- 2分解質因數_百度百科
把一個合數分解成若干個質因數的乘積的形式，即求質因數的過程叫做分解質因數。 分解質因數只針對合數。（分解質因數也稱分解素因數）求一個數分解質因數，要從最小 ...
- 3分解质因数· Prime Factorization - 九章算法
算法流程： · 从小到大遍历. [. 2,up. ] · up一般设定为sqrt(num)，因为一个数大于其根号的质因数最多只有一个，那么遍历其根号内的数可以将时间复杂度减小至根号n，若遍历完 ...
- 4【例題】利用質因數分解找出一個數所有的因數練習| 數學
影片：【例題】利用質因數分解找出一個數所有的因數練習，數學> 主題式> 國小> 數與量> 因數與倍數> 【六年級】最大公因數與最小公倍數。源自於：均一教育平台- 願每個 ...
- 5又稱素因數分解 - 中文百科知識
其他算法
