Miller-Rabin算法(转)

efforttoc — 2007-03-22 23:42:00

一.费马小定里 if n is prime and (a,n) equals one ,then a^(n-1) = 1 (mod n) 费马小定理只是个必要条件,符合费马小定理而非素数的数叫做Carmichael. 前3个Carmichael数是561,1105,1729。 Carmichael数是非常少的。在1~100000000范围内的整数中，只有255个Carmichael数。为此又有二次探测定理,以确保该数为素数: 二.二次探测定理二次探测定理如果p是一个素数，0#include #include #include typedef __int64 lltype;const int MAX_COUNT = 6;//测试次数lltype allFactor[65], nFactor;//质因分解结果(刚返回的时候是无序的)void fFindFactor(const lltype &num);//主函数(num > 1) lltype pollard_rho(const lltype &c, const lltype &num);bool miller_rabin(const lltype &n, int count);//miller-rabinbool fWitNess(const lltype &a

(转)Prime Numbers, Factorization and Eule

efforttoc — 2007-03-11 23:51:00

Prime numbers and their properties were extensively studied by the ancient Greek mathematicians. Thousands of years later, we commonly use the different properties of integers that they discovered to solve problems. In this article we’ll review some definitions, well-known theorems, and number properties, and look at some problems associated with them. A prime number is a positive integer, which is divisible on 1 and itself. The other integers, greater than 1, are composite. Coprime integers are a set of integers that have no common divisor other than 1 or -1. The fundamental theorem of arithmetic:Any positive integer can be divided in primes in essentially only one way. The phrase 'essentially one way' means that we do not consider the order of the factors important. One is neither a prime nor composite number. One is not composite because it doesn’t have two distinct divisors. If one is prime, then number 6, for example, has two different representations as a product of prime nu

类设计者的核查表

efforttoc — 2007-03-09 00:10:00

摘自<> 1.你的类需要一个构造函数吗？ 2.你的数据成员是私有的吗？ 3.你的类需要一个无参的构造函数吗？ 4.是不是每个构造函数初始化所有的数据成员？ 5.类需要析构函数吗？ 6.类需要一个虚析构函数吗？ 7.你的类需要复制构造函数吗？ 8.你的类需要一个赋值操作符吗？ 9.你的赋值操作符能正确地将对象赋给对象本身吗？ 10.你的类需要定义关系操作符吗？ 11.删除数组时你记住了用delete[]吗？ 12.记得在复制构造函数和赋值操作符的参数类型中加上const 了吗？ 13.如果函数有引用参数，它们应该是const引用吗？ 14.记得适当地声明成员函数为const的了吗？

杂类集

efforttoc — 2007-02-03 21:17:00

Great Common Divisor最大公约数 n1.Euclid算法重复gcd(a,b) = gcd(a,b mod a)至b mod a等于0 ， gcd(b,0)=b, b最后的取值为a,b初值的最大公约数 2.stein算法 1. 1.如果A=0，B是最大公约数，算法结束 2. 如果B=0，A是最大公约数，算法结束 3. 设置A1 = A、B1=B和C1 = 1 4. 如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(乘2整数左移一位，除2整数右移一位即可) 5. 5.如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (显然，2不可能为任何奇数的约数) 6. 6.如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (同上J) 7. 如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn 8. n++，转4 注：、Cn为两数最大公约数＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝给定两个任意正整数n和任一质数p,求将n!表示成算术基本定理的形式的时候，p的指数． count=0; while(n) { count+=n/p; n/=p; } cout<

hash function

efforttoc — 2006-09-29 22:02:00

经典字符串中出现的hash函数（转载自http://www.ccw.com.cn/htm/app/aprog/01_8_22_3.asp） 1． PHP中出现的字符串Hash函数 static unsigned long str_hash_function (char *arKey , unsigned int nKeyLength) { int h=0; int g; char *arEnd=arKey+nKeyLength; while (arKey>24); h=h^g; } } return h; } 2． OpenSSL中出现的字符串Hash函数 unsigned long str_hash_function (char *str) { int i , l; unsigned long ret=0; unsigned short *s; if (str==NULL) return (0); l=(strlen(str)+1)/2; s=(unsigned short *) str; for (i=0;i

计算几何算法概览(转)

efforttoc — 2006-09-06 21:28:00

怒火之袍　计算几何算法概览一、引言　　计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。二、目录　　本文整理的计算几何基本概念和常用算法包括如下内容：　　矢量的概念　　矢量加减法　　矢量叉积　　折线段的拐向判断　　判断点是否在线段上　　判断两线段是否相交　　判断线段和直线是否相交　　判断矩形是否包含点　　判断线段、折线、多边形是否在矩形中　　判断矩形是否在矩形中　　判断圆是否在矩形中　　判断点是否在多边形中　　判断线段是否在多边形内　　判断折线是否在多边形内　　判断多边形是否在多边形内　　判断矩形是否在多边形内　　判断圆是否在多边形内　　判断点是否在圆内　　判断线段、折线、矩形、多边形是否在圆内　　判断圆是否在圆内　　计算点到线段的最近点　　计算点到折线、矩形、多边形的最近点　　计算点到圆的最近距离及交点坐标　　计算两条共线的线段的交点　　计算线段或直线与线段的交点　　求线段或直线与折线、矩形、多边形的交点　　求线段或直线与圆的交点　　凸包的概念　　凸包的求法三、算法介绍　　矢量的概念：　　如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。　　矢量加减法：　　设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 -

Bellman-Ford算法

efforttoc — 2006-09-05 22:16:00

该算法用来求边上权值为任意值的单源最短路径问题伪代码如下： void bellman_ford(int v) { for 1 to n initialize dist[i][v]; //此时只经过一条边 for 2 to n-1 (i) //经过的边数不大于i条时 for 1 to n (j) //对于每一个目标顶点 for 1 to n (k) //经过该顶点时，与当前最小值比较，并更新当前值 if edge[k][j] > 0 && dist[k] > edge[k][j]+dist[j] 更新当前值 }//

LIS

efforttoc — 2006-08-20 21:04:00

#include using namespace std; #define MAXNUM 1000 char c[MAXNUM];char b[MAXNUM+1]; void solve(){ int i,first,last,mid,len; len = 1; i = 1; b[1] = c[0]; while (c[i]) { first = 1; last = len+1; while (first < last) { mid = (first+last)>>1; if (b[mid] < c[i])first = mid+1; else last = mid;

Josephus问题的数学方法(转)

efforttoc — 2006-08-20 11:02:00

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。现在我们把他们的编号做一下转换：k --> 0k+1 --> 1k+2 --> 2......k-2 --> n-2k-1 --> n-1变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]递推公式f[1]=0;f[i]=(f[i-1]+m)%i; (i>1)有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：＃i nclude main(){&

费马最後定理（转）

efforttoc — 2006-08-19 20:13:00

被公认执世界报纸牛耳地位地位的纽约时报於1993年6月24日在其一版头题刊登了一则有关数学难题得以解决的消息，那则消息的标题是「在陈年数学困局中，终於有人呼叫『我找到了』」。时报一版的开始文章中还附了一张留着长发、穿着中古世纪欧洲学袍的男人照片。这个古意盎然的男人，就是法国的数学家费马（Pierre de Fermat）（费马小传请参考附录）。费马是十七世纪最卓越的数学家之一，他在数学许多领域中都有极大的贡献，因为他的本行是专业的律师，为了表彰他的数学造诣，世人冠以「业余王子」之美称，在三百六十多年前的某一天，费马正在阅读一本古希腊数学家戴奥芬多斯的数学书时，突然心血来潮在书页的空白处，写下一个看起来很简单的定理这个定理的内容是有关一个方程式 x2 + y2 =z2的正整数解的问题，当n=2时就是我们所熟知的毕氏定理（中国古代又称勾股弦定理）：x2 + y2 =z2，此处z表一直角形之斜边而x、y为其之两股，也就是一个直角三角形之斜边的平方等於它的两股的平方和，这个方程式当然有整数解（其实有很多），例如：x=3、y=4、z=5；x=6、y=8、z=10；x=5、y=12、z=13…等等。费马声称当n>2时，就找不到满足xn +yn = zn的整数解，例如：方程式x3 +y3=z3就无法找到整数解。当时费马并没有说明原因，他只是留下这个叙述并且也说他已经发现这个定理的证明妙法，只是书页的空白处不够无法写下。始作俑者的费马也因此留下了千古的难题，三百多年来无数的数学家尝试要去解决这个难题却都徒劳无功。这个号称世纪难题的费马最後定理也就成了数学界的心头大患，极欲解之而後快。十九世纪时法国的法兰西斯数学院曾经在一八一五年和一八六０年两度悬赏金质奖章和三百法郎给任何解决此一难题的人，可惜都没有人能够领到奖赏。德国的数学家佛尔夫斯克尔（P‧Wolfskehl）在1908年提供十万马克，给能够证明费马最後定理是正确的人，有效期间为100年。其间由於经济大萧条的原因，此笔奖额已贬值至七千五百马克，虽然如此仍然吸引不少的「数学痴」。二十世纪电脑发展以後，许多数学家用电脑计算可以证明这个定理当n为很大时

string流

efforttoc — 2006-08-17 20:51:00

ostringstream类向一个string插入字符，istringstream类从一个string对象读取字符，而stringstream类可以用来支持读和写两种操作。为了使用string流,我们必须包含相关的头文件： #include 例如， string read_file_into_string() { ifstream ifile( "alice_emma" ); ostringstream buf; char ch; while(buf && ifile.get( ch )) buf.put( ch ); return buf.str(); } 成员函数str()返回与ostringstream类对象相关联的string对象。 istringstream由一个string对象构造而来，它可以读取该string对象。istringstream的一种用法是将数值字符串转换成算术值。 ---摘抄自《C++PRIME》.

最小生成树

efforttoc — 2006-08-17 15:23:00

public static void prim(int n,float [][]c){ float []lowcost = new float[n+1]; int []closest = new int[n+1]; boolean []s = new boolen[n+1]; s[1] = true; for (int i = 2; i <= n; i++) { lowcost = c[1][i]; closest[i] = 1; s[i] = false; } for (int i=1; i < n; i++) { float min = Float.MAX_VALUE; int j = i; for (int k = 2; k <= n; k++) { &n

随机排序算法

efforttoc — 2006-08-07 16:01:00

void InterChange(int a[],int i,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } int partition(int a[],int p,int q) { int v = a[p],i = p,j = q; do{ do i++; while (a[i] < v); do j--; while (a[j] > v); if (i < j)InterChange(a,i,j); }while (i < j); a[m] = a[j];a[j] = v; return j; } void RQuickSort(int a[],int p,int q) { if (p < q) { if (q-p > 5)InterChange(a,rand()%(q-p)+p,p); int j = partition(a,p,q); RQuickSort(p,j); RQuickSort(j,q); } } PS：随机排序算法的时间复杂度也是O(nlogn),但算法的平均性能是很好的。在解POJ1186题时，用分治＋二分查找算法，要用到排序，排序的对象最多有33万个，如果用qsort或sort可能会超时，但我用上面的RQuickSort就AC了。由此可见，当对象数目很多时，RQuickSort的性能要比qsort,sort要好。

“死了都要编”--改篇自信乐团"死了都要爱"（转）

efforttoc — 2006-07-28 14:58:00

死了都要编不动态规划不痛快算法多深只有这样才足够表白死了都要编不A星算法不痛快宇宙毁灭星还在把每天当成是比赛来编程一分一秒都编到汗水掉下来不理会别人是搜索或贪心只要你勇敢跟我编编不用刻意安排凭感觉去编程提交就会很愉快享受现在别一提交就怕WRONG ANSWER许多奇迹我们相信才会存在死了都要编不用后缀树不痛快算法多深只有这样才足够表白死了都要编不遗传算法不痛快宇宙毁灭基因还在穷途末路都要编不升起气球不痛快超时会TIME出错会RUN空间不会MEM到绝路都要编不AC题目不痛快不怕机房变火海编到沸腾才精采

POJ2800，Joseph's Problem解题报告

efforttoc — 2006-07-28 14:48:00

题目很简单，你的解答也很简单： int calc(int n,int k){ int ret = 0,i; for (i = 1; i <= n; i++)ret += k%i; return ret;} 可是，它怎么就超时了呢？注意约束条件： The input file contains n and k(1<= n,k <= 10^9). n的最大值是10^9。。。。你的程序不超时才怪呢？ O(n)的算法，还能怎么优化呢？对给定的K，所求为不大于n的所有正整数除K的余数r1,r2,......,rn的总和。假设它们对应的商为s1,s2,.....,sn. 注意到，商的可能取值只有O(sqrt(n))种情况，对每个可能的商的值，k%i成等差数列。容易看出，此问题的解的时间复杂度不大于O(sqrt(n)). 分析，解决问题对N，K比较小的情况，写出具体的余数和商数表。观察，分析这个表格。现在，你能否为本问题设计出复杂度为O(sqrt(n))的算法？

STL算法学习(七)

efforttoc — 2006-07-28 14:37:00

/*find_end: 函数原型： template FdwIt1 find_end(FdwIt1 first1,FdwIt1 last,FdwIt2 first2,FdwIt2 last2); template FdwIt1 find_end(FdwIt1 first1,FdwIt1 last,FdwIt2 first2,FdwIt2 last2, Pred pr); 功能：在由[first1,last1)标记的序列中查找“由iteratior对[first2,last2)标记的第二个序列”的最后一次出现。例如，已知亭子符序列mississippi和第二个序列ss，则find_end()返回一个FwdIt1指向第二个ss序列的第一个s。如果 &nbs

C++学习笔记·输入输出(4)(转)

efforttoc — 2006-07-27 19:59:00

四、格式化输入输出　　C++语言中有两种方法可以控制格式化输入输出：流对象的成员函数和操纵器。　　<1> 流对象的成员函数　　下表中的格式化标志，可以通过成员函数setf()来设置，也可以用unsetf()来复位，如果需要设置多个标志，可以使用 | 运算符(使用标志时前边加上ios::)。───────┬───────────────────────┬──── 格式化标志 │ 描述 │ 默认───────┼───────────────────────┼──── boolalpha │ 以alpha格式进行布尔输入输出 │ off showbase │ 显示8进制或16进制前缀 │ off showpoint │ 显示10进制浮点数末尾的零 &n

STL算法学习(六)

efforttoc — 2006-07-27 00:26:00

/*fill: 函数原型： template void fill(FwdIt first,FwdIt last,const T& value); 功能：将value拷贝到区间[first,last)中的每一个元素。 fill_n: 函数原型： template void fill_n(FwdIt first,Size n,const T& value); 功能：将value拷贝到从first开始的n个元素上。 find: 函数原型： template InputIterator find(InputIterator first,InputIterator last,const T&

STL算法学习(五)

efforttoc — 2006-07-24 17:37:00

/*equal: 函数原型： template bool equal(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2); template bool equal(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2, Predicate pred); 功能：第一个版本将序列[first1,la

STL算法学习(四)

efforttoc — 2006-07-22 16:51:00

/*count: 函数原型： template typename iterator_traits::difference_type count(InputIterator first,InpurIterator last,const Type& value); 功能：在序列[first,last)中查找和value相等的元素个数，统计其个数，返回其值。 count_if: 函数原型: template typename iterator_traits::difference_type count_if(InputIterator first,InputIterator last,Predicate pred); 功能：在序列[first,last)中统计满足关系pred的元素个数，并返回其值。

argol