资源描述：
《关于整数的整数因子和问题的若干研究.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、关于整数的整数因子和问题的若干研究摘要：最近在做一些ACM关于数论的题目时，经常会遇到要求出一个整数的整数因子和的问题，于是下决心把这个问题研究清楚。最终得出了一个还算不错的结果，该结果对于很大范围的整数部适用，不管是效率还是代码的简洁程度都是不错的。这个结果的得来主要用到了算术基本定理，鸽巢原理，及组合数学、二分快速幕算法等相关知识。关键词：桀数因子和算术基本定理鸽巢原理第一次遇到整数的整数因子和问题是在做hduoj的1452—一Happy2004：题目如下：ProblemDescriptio
2、nConsiderapositiveintegerX.andletShethesumofallpositiveintegerdivisorsof2004^X.YourjobistodetermineSmodulo29(therestofthedivisionofSby29).TakeX=1foranexample.Thepositiveintegerdivisorsof20047are/,2,3,4,6,12,167,334,501,668,1002and2004.ThereforeS=4704
3、andSmodulo29isequalto6.InputTheinputconsistsofseveraltestcases.EachtestcasecontainsalinewiththeintegerX(1<=X<=10000000).AtestcaseofX=0indicatestheendofinput,andshouldnotbeprocessed.OutputForeachtestcase,inaseparateline,pleaseoutputtheresultofSmodulo2
4、9.SampleInput1100000SampleOutput610这个题目的关键就是要求出2004AX的整数因了和。对于这个问题最为常见的思路就是模拟了：从1到[sqrt(2004AX)]Z间的数逐个试除，如果判断为其因了，那么就加到sum+o这个思路大复杂度为显然为0(20.5)对于很小的粥数或许还可以，但是对于本题的n=2004AX(1<=X<=10000000)来说显然是不行的。对这个问题的进一步研究表明，整数的因了问题一般最后的木质实际上都是素数因了的问题。这里引入算术基本定理：算术
5、基本定理,又称为正整数的唯一分解定理,BP：每个大于I的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。X3x17：1200=x3x算术基本定理的内容由两部分构成:-分解的存在性:-分解的唯一性,即若不考虑排列的顺序,正整数分解为素数乘积的方式是唯一的。算术基木定理是初等数论中一个基木的定理，许多的数论问题最终都可以归结为算术基木定理的灵活应用。这里举一个很多人都知道的应用：怎么算出一个整数N的因子个数？我们对N进行标准分解可以得到形如：fj"（〃为素数）/=11那么有结
6、论N的因子个数为：flQx+1）。那么这个问题与算术基本定理有什么联系呢？考察上面的那个例了时，如果仔细想因了个数公式的推导过程，可以发现实际上，任何一个N的因子的都可以这样得到：在构成的集合屮，我们可以做这样的选择，选择井，p打P?……琦那么我们恰共有（©+1）种不同的选择，利用乘法原理可以很容易得出N的因子个数公式。上面的推导过程是一个组合的过程，实际上我们己经完成了N的所有的因子的组合的T作。请看下式：k口（M+P；++Pi'）/=1如果你在纸上写下它，然后展开，你会惊奇的发现，所有的N的
7、因子都在展开式中出现了，不重不漏！回到因子个数的思考过程，它们是不是有异曲同丁•之妙呢？！得到这个式子意味着，我们并不需要求出N的所有因子，只需要对其进行标准分解即可。这个时候1〜"64之间的数，运用这个方法儿乎都可以很快解出答案。我们处理问题的速度和范围都大大的提高了。但是进一步：实际中我们经常需要求出的是因子和对一个数的模，而非求出这个数（这个主要限于现在计算机的发展，实际上求出对一个数的模，和求出这个数是等价的——只要计算机发展到能计算足够大的数，那么我们就可以用相同的算法求出实际要求的数
8、）。而且，涉及到的N也并不是只有1〜"64这么大的范围。对于更大的数，“本身的指数兔可能就是一个很大的数（兔＞10八6）,当然这个时候我们会想到用二分幕来快速求解，解决方案中也的确用到了二分屣，但是细节问题却是这样的：ri(p°+H+〃；+……+p")1=1等比数列求和公式这个式子对一个数求模，我们口然会把求模分配到每一个因式中，如果能进一步分配到次方求模，那么我们就可以直接用二分幕十分完美的解决这个问题了。但是偏偏结果中存在一个除的运算！我们不能进一步分配进去了……经过分析，发现有两种解决的方
