在Miller Rabbin测试素数这篇文章里的Modular_Exp函数里，就用到了快速幂取模的思想。 这里总结下。 求a^b%c（这就是著名的RSA公钥的加密方法） 当a,b很大时，直接求解这个问题不太可能 你能想到哪些优化呢？ 算法1：直观上，也许最容易想到的是利用a*b%c=((a%c)*b)%c,这样每一步都进行这种处理，这就解决了a^b可能太大存不下的问题，但这个算法的时间复杂度依然是O(n)，根本没有得到优化。当b很大时运行时间会很长 算法2：另一种算法利用了二分的思想，可以达到O(logn)。 可以把b按二进制展开为b=p(n)*2^n+p(n-1)*2^(n-1)+…+p(1)*2+p(0) 其中p(i) (0
伪素数：如果n是一个正整数，如果存在和n互素的正整数a满足a^n-1≡1(mod n)，我们说n是基于a的伪素数。如果一个数是伪素数，它几乎肯定是素数。（即下面的费马小定理） 费马小定理是数论中的一个重要定理,其内容为: 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡１（mod p） 假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1。 更多关于费马小定理请参阅： http://baike.baidu.com/view/263807.htm?fr=ala0_1 这是Miller Rabbin测试素数的代码模版： 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 [...]
题目地址： http://acm.hdu.edu.cn/showproblem.php?pid=1262 就这样的代码居然是0MS~~~ 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 // Author: Tanky Woo // HDOJ 1262 #include <iostream> using namespace std; bool Is_prime(int n) { for(int i=2; i*i<=n; ++i) if(n%i==0) return 0; return [...]
题目地址： http://acm.hdu.edu.cn/showproblem.php?pid=1431 看见大家都打表了。。。我也赶时髦，和大家一起打表，水过~~~~ // 下面是这个是先求表的 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 #include <cmath> const int MAX = 100000001; const int SQRT = sqrt(MAX); bool prime[MAX] [...]
最近更新时间：2011.10.8 The Sieve of Eratosthens 爱拉托逊斯筛选法 思想：对于不超过n的每个非负整数P，删除2*P, 3*P…，当处理 完所有数之后，还没有被删除的就是素数。 若用vis[i]==1表示已被删除，则代码如下： —————————————————– 代码一： 1 2 3 4 memset(vis, 0, sizeof(vis)); for(int i = 2; i <= 100; i++) for(int j = i*2; j <= 100; j += i) vis[j] = 1; 上面的代码效率已经很高了。 但还可以继续优化。 看一个改进的代码： —————————————————— 代码二： 1 2 3 4 5 6 7 8 9 10 [...]