加载中…
个人资料
Patrick
Patrick
  • 博客等级:
  • 博客积分:0
  • 博客访问:22,509
  • 关注人气:3
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
访客
加载中…
好友
加载中…
评论
加载中…
留言
加载中…
分类
博文
标签:

acm

数学

it

分类: ACMer
素性检测方法就是检测一个数是否具有素数的特性。也就是说一个数满足检测素性方法只是它是素数一个必要条件。而Rabin-Miller强拟素性检测就是这样一种方法。所以,用此方法证明一个数是否为素数存在一定误差。

强拟素性检测法利用的是费马小定理。
若p为素数且gcd(b,p)=1 则 b^(p-1) mod p = 1         (真命题)
逆命题:
若n为正奇数,gcd(b,n)=1且b^(n-1) mod n != 1 则n一定为合数。  (真命题)
上述命题假设:
若n为正奇数,满足b^(n-1)mod n = 1  则n一定为素数。 (假命题)
这就是Rabin-Miller需要的素数假设。
公式描述:
b^(n-1)mod n = 1
对于存在上式的n,n称为是以b为基的概素数。
如果n为合数,则称n是以b为基的伪素数。
故:概素数=素数+伪素数。

有趣的是,对于费马小定理扩展出的Rabin-Miller算法,这样的伪素数相对与素数并不多。
对于以2为基数的伪素数,前10000000只有750个。
如果使用多个基数检测, 则这个数目将会更小。

这里有一个误区:随机数检测法,虽然以随机数作为基数
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-05-06 19:06)
标签:

acm

c

poj

数学

杂谈

分类: ACMer

取石子游戏
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 23080
Accepted: 7190

Description

有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。

Input

输入包含若干行,
阅读  ┆ 评论  ┆ 禁止转载 ┆ 收藏 
(2011-05-04 16:13)
标签:

acm

c

poj

数学

杂谈

分类: ACMer
Perfection
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 7890
Accepted: 3788

Description

From the article Number Theory in the 1994 Microsoft Encarta: ``If a, b, c are integers such that a = bc, a is called a multiple of b or of c, and b or c is called a divisor or factor of a. If c is not 1/-1, b is called a proper divisor of a. Even integers, which include 0, are multiples of 2, for example, -4, 0, 2, 10; an odd integer is an integer that is not even, for example, -5, 1, 3, 9. A perfect number is a positive integer that is equa
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-04-27 20:36)
标签:

acm

c

poj

数学

教育

分类: ACMer
Moo Volume
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 13475 Accepted: 3906

Description

Farmer John has received a noi
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

acm

poj

c

数学

教育

分类: ACMer
Number Sequence
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 23398 Accepted: 6243

Description

A single positive integer
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-04-26 16:42)
标签:

acm

c

poj

数学

教育

分类: ACMer
Code
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 4683 Accepted: 2149

Description

Transmitting and memorizing inf
阅读  ┆ 评论  ┆ 禁止转载 ┆ 收藏 
(2011-04-25 16:42)
标签:

acm

数学

poj

c

教育

分类: ACMer
Round Numbers
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 4233 Accepted: 1395

Description

The cows, as you k

阅读  ┆ 评论  ┆ 禁止转载 ┆ 收藏 
标签:

杂谈

分类: 杯具洗具

看的我心都凉了!!!有木有啊!!!

 

学通信的海纸你们

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-02-08 10:27)
标签:

acm

c

hdu

教育

分类: ACMer

Big Event in HDU

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7128    Accepted Submission(s): 2370


Problem Description
阅读  ┆ 评论  ┆ 禁止转载 ┆ 收藏 
(2011-02-01 10:20)
标签:

acm

c

hdu

杂谈

分类: ACMer

I NEED A OFFER!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5184    Accepted Submission(s): 1782


Problem Description
阅读  ┆ 评论  ┆ 禁止转载 ┆ 收藏 
  

新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有