【申精】【小知识】来一碗质因数分解_pascal吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：6,637贴子：
【申精】【小知识】来一碗质因数分解收藏
来一碗质因数分解一、前言
质因数分解，是一个在算法竞赛里老生常谈的经典问题。我们在解决许多问题的时候需要用到质因数分解来辅助运算，而且质因数分解牵扯到许许多多经典高效的算法，例如miller-rabin判断素数算法，rho启发式搜索质因数分解算法等。在此文里，我要介绍的就是miller-rabin算法以及rho启发式搜索分解算法。二、算术基本定理
首先，我们得知道，任意一个大于1的自然数都可以分解为有限个质数的乘积，。这里均为质数，且为正整数。我们把这样的分解成为N的标准分解式。关于算数基本定理的应用有许多，例如可以证明素数无限，定义god,lcm等，在此不一一赘述。有了算数基本定理，我们可以发现计算数论函数，约数和等都是十分方便的，这大大的方便了我们的解题。接下来我们介绍如何来分解质因数。三、质因数分解的算法所谓质因数，是某自然数的因素而且这个因素还得是质数。我们不难想到基本的枚举，即暴力枚举1~n所有数，判断是否能够被n整除且该数是否为质数。大概代码如下：For i:=1 to n do
If n mod i=0 then
If check(i) then
//check为检验i是否为质数的子函数，返回值为boolean
Writeln(i); Function check(n:longint):Var i:begin
For i:=2 to n do If n mod i=0 then exit(false); //如果一旦有比它小的数除他为0，那么该数不为质数
Exit(true); //否则显然为质数E
这个是最朴素的方法，虽然代码简洁思路简单，但是时间复杂度实在是太高了。于是我们有了优化1，我们发现判断一个数是否为素数只需枚举到sqrt(i)，为何呢？因为一个数若不是素数，那么它必定是两个数的乘积，这两个数显然有一个小于等于sqrt(i)，否则sqr(sqrt(i))=i，那么显然为质数。Function check(n:longint):Var i:Begin For i:=2 to sqrt(n) do
If n mod i=0 then exit(false);Exit(true);E但是我们发现时间复杂度还是比较高O(sqrt(n)*n)于是我们有了优化2。我们不暴力判断n的每个因素，而是不断去试除。何谓试除？设x是n的质因数，我们在分解的过程中每找到一个x就把它记录下来，并且让n:=那么我们在遇见x的倍数时，显然不可能会再有x的倍数了。那么我们就能通过“类似筛法”的思想，在O(sqrt(n))时间内，对n进行质因数分解，这也是现在比较常用的方法。I:=2;While n&&1 do BeginWhile n mod i=0 do BeginWriteln(i);N:=EInc(i);E我们在不断的div i中，我们把i的所有存在于n的因素里的倍数全部给丢掉了。（即，n=12时，n=2*2*3=3*4 那么我们在i=2的时候，把4给筛掉了。）在这里，我们发现每个i都会是质数，即i的变化总是2→3→5→7.......于是我们有了优化3。如果我们能预先存储不大于sqrt(n)的所有质数，我们就可以快速调用了，不要小看这个优化，在n的质因数比较大的时候，O(n)的线性时间是我们耗费不起的。先来说下筛法（摘自百度百科）用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。如有：1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 301不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是：3 5 7 9 11 13 15 17 19 21 23 25 27 29剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为：2 3 5 7 11 13 17 19 23 29 procedure get(n:longint);
//Get函数为利用筛法求素数var maxfactor,newp:begin
maxfactor:=trunc(sqrt(n));
fillchar(hash,sizeof(hash),true);
for i:=2 to maxfactor do
if hash[i] then
newp:=i shl 1;
//等价于newp:=i*2;
while newp&n do
hash[newp]:=
inc(newp,i);
for i:=2 to n do
if hash[i] then
inc(sushut);
sushu[sushut]:=i; procedure solve(n:longint);var i:begin
while sushu[i]&=n do
if sushu[i]=0
while n mod sushu[i]=0 do
n:=n div sushu[i];
if tot=1 then
sum[ans].number:=sushu[i];
sum[ans].k:=
if sushu[i]=2 then fuck:=
inc(i); 可是这样的复杂度在n为超大整数类型且素因子十分大的时候也无能为力了，不仅会MLE，更会TLE。那么，我们来说一下这次的重头戏，也就是rho分解大法。我们必须知道Fermat分解：
首先，对于任意的一个偶数，我们都可以提取出一个2的质因子，如果结果仍为偶数，则可继续该操作，直至将其化为一个奇数和2的多少次幂的乘积，那么我们可以假定这个奇数可以被表示成2*N+1，如果这个数是合数，那么一定可以写成N=c*d的形式，不难发现，式中的c和d都是奇数，不妨设c&d，我们可以令a=(c+d)/2,b=(c-d)/2，那么的可以得到N=a*a-b*b，而这正是Fermat整数分解的基础；由不等式的关系，我们又可以得到a&=sqrt(c*d)=sqrt(N)，那么，我们就可以枚举大于N的完全平方数a*a，计算a*a-N的值，判断计算的结果是否为一个完全平方数，如果是，那么a，b都是N的因子，我们就可以将算法递归的进行下去，知道求出N的所有质因子。容易看出，Fermat分解大数的效率其实并不高，但是比起试除法要好了很多；而且每次的计算都是计算出N的一个因子，更加降低了其效率。这就让我们想着去尝试新的算法，那就是Pollard rho算法。
Pollard rho算法的原理就是通过某种方法得到两个整数a和b，而待分解的大整数为n，计算p=gcd(a-b,n)，直到p不为1，或者a，b出现循环为止。然后再判断p是否为n，如果p=n成立，那么返回n是一个质数，否则返回p是n的一个因子，那么我们又可以递归的计算Pollard(p)和Pollard(n/p)，这样，我们就可以求出n的所有质因子。
具体操作中，我们通常使用函数x2=x1*x1+c来计算逐步迭代计算a和b的值，实践中，通常取c为1，即b=a*a+1，在下一次计算中，将b的值赋给a，再次使用上式来计算新的b的值，当a，b出现循环时，即可退出进行判断。 在实际计算中，a和b的值最终肯定一出现一个循环，而将这些值用光滑的曲线连接起来的话，可以近似的看成是一个ρ型的。
对于Pollard rho，它可以在O(sqrt(p))的时间复杂度内找到n的一个小因子p，可见效率还是可以的，但是对于一个因子很少、因子值很大的大整数n来说，Pollard rho算法的效率仍然不是很好，那么，我们还得寻找更加的方法了。有了上述预备知识还不够，我们还得知道miller-robin素性检验。根据费马小定理，若n是一个奇素数，a是任何整数(1≤ a≤n-1) ，则 a^(n-1)≡1(mod n)。miller-robin的理论基础：如果n是一个奇素数， 将n-1表示成2^s*r的形式(r是奇 数)，a 是和n互素的任何整数， 那么ar≡1(mod n) 或者对某个j(0≤j ≤s －1， j∈Z) 等式 a2jr ≡－1(mod n)成立。 这个理论是通过一个事实经由Fermat定理推导而来： n是一个奇素数，则方程x2 ≡ 1 mod n只有±1两个解。注意，miller-rabin算法只是一种素性判断的概率算法，关于miller-rabin，pascal贴吧里应该有相关的帖子介绍，而miller-rabin的判断错误的概率是相当低的，(0.25)^t，t为素性测试的轮数。Miller-rabin算法在Int64范围内无法解决的强伪素数特殊判断一下即可。接下来我们上代码：（我没找到Pas的，于是自己写了一份很丑的Pas代码，大神勿喷）const count=10;
pri:array [0..10] of longint=(2,3,5,7,11,13,17,19,23,29,31);
var n,total:int64;
ans:array [0..10000] of int64; function multi(a,b,m:int64):int64;//考虑到64位二进制数能表示的范围，只需取前9个素数为基var ans:int64;begin
while b&&0 do
if (b and 1)=1 then
ans:=(ans+a)
exit(ans); function gcd(x,y:int64):int64;begin
if x mod y=0 then
else exit(gcd(y,x mod y)); function quick_mod(a,b,m:int64):int64;var ans:int64;begin
ans:=1; a:=
while b&&0 do
if (b and 1)=1 then
ans:=multi(ans,a,m);
a:=multi(a,a,m);
exit(ans); function prime(n:int64):var m,k,a,x,y:int64; i,j:begin
if n=2 then exit(true);
if (n&2) or ((n and 1)=0) then exit(false);
m:=n-1; k:=0;
while (m and 1)=0 do
for i:=0 to count do
a:=random(n) mod (n-1)+1;
x:=quick_mod(a,m,n);
for j:=0 to k-1 do
y:=multi(x,x,n);
if (y=1) and (x&&1) and (x&&n-1) then exit(false);
if y&&1 then exit(false);
exit(true);
function pollard_rho(n,c:int64):int64;var i,k,x,y,d:int64;begin
i:=1; k:=2;
x:=random(n) mod (n-1)+1;
while true do
x:=(multi(x,x,n)+c)
d:=gcd(y-x,n);
if (d&1) and (d&n) then exit(d);
if (x=y) then exit(n);
if (i=k) then
k:=k&&1; procedure find(n,c:int64);var p,k:int64;begin
if prime(n) then
inc(total);
ans[total]:=n;
while p&=n do
p:=pollard_rho(p,c);
find(p,k);
find(n div p,k); begin
find(n,120);
for i:=1 to total do
writeln(ans[i]);end. 至此，我们在Int64范围内解决了质因数分解的若干问题。By:罗不理百度缩进太可耻，要原docx文件可以联系本人。。
有一点没看懂，能解释的清楚点吗？
我竟然看完了
好顶赞 能在百度找到这些也不容易了
登录百度帐号我的游戏推荐游戏
后查看最近玩过的游戏
为兴趣而生，贴吧更懂你。或分解因数pascal_百度知道
分解因数pascal
如何得到一个数所有因数（注意，不是质因数）的和？不用循环，数特别大......pascal用
数很大，时间太长 算了直接来题吧 还是不够长芝麻开门提交文件名：ZMKM.PAS 问题描述：
周末小可可参加智力大冲浪活动，经过努力终于l来到最后一关“芝麻开门”。门上的电子显示屏写着这么一段话：如果你能把NK的所有正整数因子的和正确地写在门上，并念一声“芝麻开门”，门就能够自由打开。
例如：n=2、k=3,则nk=8,它的正因子有1、2、4、8，如果小可可把它们的和15写在门上，然后念一声“芝麻开门”门就能够自动打开。
已知门上的n、k都是每过一段时间就会变化一次，请你编写程序协助小可可在规定的时间内求出答案，从而获得智力大冲浪的最终大奖。
从键盘输入两个自然数n和k,1&=n&=2的16次方,
打印输出问题的解（解的位数不超过100位）。 注意范围 在讲解以下
提问者采纳
什么叫不用循环...虽然用了循环，但是时间复杂度是O(sqrt(n))的，速度比O(n)的快很多，longint内的数都可以瞬间出解。{$R+,Q+,S+}var
ans,s,temp : int64;begin
readln(n);
for i:=2 to trunc(sqrt(n)) do
if m Mod i=0 then
s:=1; temp:=1;
while m Mod i=0 do
temp:=temp*i;
ans:=ans*s;
if m&1 then ans:=ans*(m+1);
writeln(ans);end. -------------------------------------------------------------------早说嘛，又不是一般性的大数，而是幂的形式，一样的方法分解N，将质因子的指数乘以k就可以了，只是要加高精度。注 ： zy是高精度数，plus为加法，multiply是高精度数乘低精度数，high_multiply是高精度数乘高精度数，看看就懂了。时间复杂度是O(sqrt(n)*L)，L是高精度位数，在题中也就是100。下面是程序 ：{$R+,Q+,S+}const
bit = 10;type
zy = array[0..102]var
n,m,i,j,k,tot :
ans,s,temp
:procedure print(a : zy );var
for i:=a[0] downto 1 do write(a[i]);function plus(a,b : zy ):var
i,len :begin
fillchar(c,sizeof(c),0);
if a[0]&b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do
inc(c[i],a[i]+b[i]);
inc(c[i+1],c[i] Div bit);
c[i]:=c[i] M
if c[i+1]&0 then inc(len);
c[0]:= exit(c);function multiply(a : b : longint ):var
i,len :begin
fillchar(c,sizeof(c),0);
len:=a[0];
for i:=1 to len do
inc(c[i],a[i]*b);
inc(c[i+1],c[i] Div bit);
c[i]:=c[i]
while c[len+1]&0 do
inc(c[len+1],c[len] Div bit);
c[len]:=c[len] M
c[0]:= exit(c);function high_multiply(a,b : zy ):var
i,j,len :begin
fillchar(c,sizeof(c),0);
len:=a[0]+b[0]+1;
for i:=1 to a[0] do
for j:=1 to b[0] do
inc(c[i+j-1],a[i]*b[j]);
inc(c[i+j],c[i+j-1] Div bit);
c[i+j-1]:=c[i+j-1] M
while (len&1) and (c[len]=0) do
c[0]:= exit(c);begin
readln(n,k);
ans[0]:=1; ans[1]:=1;
for i:=2 to trunc(sqrt(n)) do
if m Mod i=0 then
while m Mod i=0 do
tot:=tot*k;
s[0]:=1; s[1]:=1;
temp[0]:=1; temp[1]:=1;
for j:=1 to tot do
temp:=multiply(temp,i);
s:=plus(s,temp);
ans:=high_multiply(ans,s);
if m&1 then
s[0]:=1; s[1]:=1;
temp[0]:=1; temp[1]:=1;
for j:=1 to k do
temp:=multiply(temp,m);
s:=plus(s,temp);
ans:=high_multiply(ans,s);
print(ans);end.
提问者评价
其他类似问题
按默认排序
其他3条回答
不用循环不行吧！
var a,b,c,sum:begin
for b:=1 to a dobegin
if a mod b=0 then
write(sum);end.
var s,i,n:begin readln(n); s:=1+n; for i:=2 to trunc(sqrt(n)) do if n mod i=0 then s:=s+i+ if sqr(trunc(sqrt(n)))=n then s:=s-trunc(sqrt(n));//如果是平方数 writeln(s);end.
如果你的n如果足够大，那么它的因数和一定比他大许多，所以会超界（maxlongint=）……所以你的n不够大，所以用楼上的就可以解决……
pascal的相关知识
您可能关注的推广
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁pascal编程题， 编程求具有M（m&65536）个约数的最小自然数_noip吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：13,099贴子：
pascal编程题， 编程求具有M（m&65536）个约数的最小自然数收藏
RT 求神牛。大概是搜索题，先把m质因数分解，然后对因子进行搜索..但是知道怎么做还是不会做啊...据某神牛说可以动归深搜..
- - 用那个筛素数的筛法反着筛回去？
先质因数分解 然后预处理质数表 分解出来的最大的质因数减1就是目标数中质数表的第一小的数的个数。第二大的质因数减1就是目标数中质数表的第二小的数的个数。快速幂加高精乘即可
这个方法有问题,当M=8时用这个方法是30,实际上是24
貌似DP的样纸。。。
DP[i][j] = DP[i - 1][j / k] * prime[i] ^记忆化搜索应该可以吧。。。
一个数的约数个数等于其质因数分解后各质因数指数+1再做乘积于是可以乱搞了
据说数据太弱然后这样可以过八个。
额。。因为M&2^16。。所以用到不会超过前16个素数。。DP吧囧。。
约数个数有公式的，例如24=2^3*3，24就有(3+1)(1+1)=8个约数。于是最好的做法就是把约数个数分解因式，对于每一种可能的质数组合都用最小的质数算出来（按照幂降序取升序的质数）然后找出最小值就行。所以说，有时候数学对计算机很重要，说不定能够秒杀。例如USACO 2月铜牌组第三题，那个递归可以用差分方程找出通解，于是就秒杀了
没有问题，要把所有可能都拿去算，最后拿来比较
那其实还是深搜吧..
我的意思是，假如约数有24个，则24=2*2*2*34*2*34*62*2*62*128*324全部减去一，降序后，然后质数从小到大一个个乘
对啊 就是这么搜的啊..
——————求此题的代码
————————被老师催作业的孩子伤不起啊！
登录百度帐号我的游戏推荐游戏
后查看最近玩过的游戏
为兴趣而生，贴吧更懂你。或}