G-rated

What are you waiting for?

0%

本文讨论的背景是算法竞赛。

算法竞赛中最常用的筛素数算法是埃式筛法:

1
2
3
4
5
6
7
8
9
10
11
const int N = 1000010;
int vis[N], n, prime[N];

void init() {
n = 0;
memset(vis, 0, sizeof vis);
for (int i = 2; i <= 1000000; ++i) if (!vis[i]) {
prime[n++] = i;
for (int j = i + i; j <= 1000000; j += i) vis[j];
}
}

这个算法的时间复杂度还不错,要筛出 10^6 以内的素数,效率是能接受的;但要筛出 10^7 以内的素数就很吃力了,大部分情况下都会超时。

另外,这个算法的空间复杂度是O(n)(需要 vis 数组进行标记),要想筛出 10^8 或更大规模的素数时,内存会成为限制;因此,埃式算法看起来并不适合处理大素数相关的问题。

我们下面来讨论一点算法竞赛中和大素数相关的问题,首先我们定义什么是本文所指的大素数:算法竞赛中无法用埃式筛法筛出来的素数

例如,我们要判断 [1, 10^9] 中的某个数字 X 是否为素数,这属于大素数问题吗?不属于,因为只需要找出 sqrt(10^9) 以内的素数,逐一判断是否为 X 的素因子即可,筛选 sqrt(10^9) 以为的素数在埃式算法的能力范围内。

再比如,我们要判断 [1, 10^18] 中的某个数字 X 是否为素数 ,属于大素数问题吗?在本文的讨论范围内,是大素数问题,因为似乎要筛选出 sqrt(10^18) 以内的素数才能解决这个问题,这超过了埃式筛法的能力。

再比如,找出 [1, 2^31-1] 中的所有素数,属于大素数问题吗?当然属于,埃式算法办不到。

两种常用的大素数相关算法

使用 Miller Rabbin 测试算法判断一个数字是否为素数

  • 费马小定理:p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)
  • 伪素数:n是正整数,且gcd(a,n)=1,且a^(n-1)≡1(mod n),称n是基于a的伪素数
  • 如果一个数字是伪素数,那它很可能是一个素数

算法描述:

  • 对于一个正整数 n,不断枚举 [1, n-1] 内的数字 a,假如都满足 a^(n-1)≡1(mod n),则判断 n 为质数

算法竞赛中的代码实现:

  • random [1, n-1] 中的数字,用快速幂取模计算出 (a^(n-1))%n 是否为1

筛出某个区间内的大素数(前提是这个区间的长度不大,例如在 10^6)

  • 例如筛出 [2^30, 2^30 +10^6] 内的素数,这个区间内的素数都是大素数,但这个区间的长度只有 10^6
  • 典型题目 POJ 2689 Prime Distance

算法描述:

  • 埃式筛法的延伸,二次筛法
  • 由于区间长度在可接受的访问内,因此把这个区间的合数都去掉,剩下的就是素数
  • 埃式筛法每次都会筛掉某个素数的倍数;因此找出小素数(例如 10^6 以内的素数),枚举小素数,然后筛掉区间内每个小素数的倍数

对于大素数问题,利用问题性质进行分析,而不是强行筛素数

我们有了 Miller Rabbin 测试算法后,要判断任何一个 int64 以内的数字是否为素数是没有问题的。

但是要找出 int64 里面的所有素数是不可取的,因为即使有最优的时间复杂度算法,单单要用数组将这些素数存起来都无法办到。

很多大素数问题,看上去似乎要筛出所有素数,实际上题目中都提供了很多限制条件,要善于利用这些条件,挖掘性质,避免陷入找出所有大素数的思维定势中

总结

  • 埃式筛法不仅能筛出小素数,很多大素数问题也可以通过埃式筛法的延伸解决
  • 使用 Miller Rabbin 测试算法判断一个数字是否为素数
  • 善于利用题目中的特殊条件,发掘性质
  • 避免陷入企图找出所有大素数的思维定势

当我结束了自己的ACM生涯和大学生涯时,没有留下任何文字,如今想来,有些可惜;时隔多年,即便想重新回顾一番,也已经失去大半意义。

我马上要离开北京了,意识到这座城市,这几年的生活,对我整个人生应该会有深远的影响,因此这次我决定要用文字记录下来。落笔时的情绪更多地代表当下,多年后回头看,难免会觉得有些许别扭,因此这篇文章,我尽可能地以叙事为主,不带入过多的情感。

Read more »

Gonglin91 已经从 WordPress 换为 Hexo。
WordPress文章全部归档于此处,文章原链接将继续保留。
旧的文章在将来还可能会更新,但不参与 Hexo 的 posts 数统计,也不参与 categories 和 tags 的分类。
感谢一直以来对 Gonglin91 的支持。

题目链接: Recover the String

题意:

一个只包含01且不为空的字符串,在串中任意选两个不同的字符,可能产生的组合为’00’, ‘01’, ‘10’, ‘11’;
现在给你每个组合的个数a(00), a(01), a(10), a(11),在满足组合个数的条件下,构造这个串;
例如**a(00) = 1, a(01) = 2, a(10) = 2, a(11) = 1, 满足条件的串可能有:0110,1001**等

Read more »

题目链接:Complete The Graph

题意:

给出一个无向图,每个边的权重都是正整数;现在有一些的边的权重丢失了,用0表示,需要给这些边补回正整数的权重,使得补充后,从起点S到终点T的最短路恰好等于L;给出任意一个补充的方案;如果无法构造出这样的图使得S到T的最短路等于L,输出NO。

Read more »

题目链接:Ability To Convert

题意:

输入有两行,第一行的数字表示K进进制,例如16表示16进制,2 <= K <= 10^9。第二行是一个字符串S,由纯数字组成,你可以将这个字符串进行分割,对应为K进制每一位。例如K=16,S=”11311”,可以将S分割为”1”, “13”, “11”,则对应为 1*16^2 + 13*16^1 + 11*16^0;也可以分割为”11”, “13”, “11”;但不能分割为”113”, “11”,因为”113”已经超过16,不能用来表示16进制。

怎么分割S,使得这个K进制数转化为10进制时最小,例如上面的S,分割为”1”, “13”, “11”,475 = 1*16^2 + 13*16^1 + 11*16^0,转化为10进制数为475,是最小的。输出最小的10进制结果。

Read more »

大纲

  • MapReduce设计方案

    • 整体架构与执行流程
    • master设计
    • 如何容错
      • worker故障
      • master失败
    • 存储,调度与带宽
    • 如何切分任务
    • 预测执行
  • MapReduce特性和扩展功能

    • 分区函数
    • reduce顺序处理
    • combiner函数
    • 输入输出类型支持
    • 自动忽略坏数据
    • local引擎支持
    • job状态监控
    • counter
Read more »