数论中的定理

定理一:

素数定理:

定理二:设a>1,m,n>0,则

HDU2685就用到上述定理。

定理三:设a>b,(a,b)=1,则

定理四:设,那么G的值为:

n为素数:本身

n有多个素因子:1

n只有一个素因子:该因子

应用题目:HDU2582.

定理五:,其中为斐波那契数列。

定理六:给定A和B,A和B互质,最大不能组合数为A*B-A-B,不能组合数的个数为

证明:

Gcd(A, B) = 1,Lcm(A, B) = AB

把所有整数划分成A个等价类,每个等价类由相互同余的整数组成任何数分成A个剩余类,分别为 :

Ak,Ak+1,Ak+2,……,Ak+(A-1),分别记为{0(mod A)},{1(mod A)}……

而B的倍数肯定分布在这A个剩余类中,因为Gcd(A,B)=1,所以每个剩余类中都有一些数是B的倍数,并且是平均分配它的

旁证,可见HDOJ 1222 Wolf and Rabbit

设 kmin = min{k|Bk∈{i(mod A)}},i ∈ [0, A)

则 Bkmin 是{i (mod A)}中B的最小倍数。特别的,AB ∈ {0 (mod A)}

Bkmin 是个标志,它表明{i(mod A)}中Bkmin 后面所有数,即Bkmin + jA必定都能被组合出来

那也说明最大不能组合数必定小于Bkmin

我们开始寻找max{ Bkmin },Lcm(A, B) = AB,所以很明显(A-1)B是最大的

因为(A-1)B是Bkmin 中的最大值,所以在剩下的A-1个剩余类中,必定有比它小并且能被A和B组合,这些数就是:

(A-1)B-1,(A-1)B -2,……,(A-1)B -(A-1),所以最大不能被组合数就是(A-1)B -A=AB-A-B

如果A和B不互素,那{1 (mod A)}不能被A组合,同样也不能被B和A组合

我们能求出各个剩余类的Bkmin之后,不能组合数的个数就是每个剩余类中小于各自Bkmin的数的个数总和。

观察如下:A = 5,B = 3

{0(mod 5)}:0,5,10,15……
{1(mod 5)}:1,6,11,16……
{2(mod 5)}:2,7,12,17……
{3(mod 5)}:3,8,13,18……
{4(mod 5)}:4,9,14,19……

红色的就是不能组合数,可以看出在剩余类中它的数目有规律:S = [0+1+2] + [0+1]

因为A和B互质,必有一个不完全周期。

整理后得到结果为:

定理七:

定理八:设,则有以下两个结论成立:

(1)

(2)

典型题目:SPOJ11239  Code:NUMTRYE

--来自苟神 acdreamer

http://blog.csdn.net/acdreamers/article/details/7909480 

时间: 2024-11-05 12:24:43

数论中的定理的相关文章

每个程序员都应该知道的基础数论

这篇文章讨论了数论中每个程序员都应该知道的几个重要概念.本文的内容既不是对数论的入门介绍,也不是针对数论中任何特定算法的讨论,而只是想要做为数论的一篇参考.如果读者想要获取关于数论的更多细节,文中也提供了一些外部的参考文献(大多数来自于 Wikipedia 和 Wolfram ). 0. 皮亚诺公理 整个算术规则都是建立在 5 个基本公理基础之上的,这 5 个基本公理被称为皮亚诺公理.皮亚诺公理定义了自然数所具有的特性,具体如下: 0是自然数; 每个自然数都有一个后续自然数; 0不是任何自然数的

费马小定理

费马小定理是数论中的一个定理:假如a是一个整数,p是一个质数,那么 如果a不是p的倍数,这个定理也可以写成

《数论概论(原书第4版)》一第1章 什么是数论

第1章 什么是数论 数论研究正整数集合 1,2,3,4,5,6,7,-, 它也常被称为自然数集合.特别地,我们要研究不同类型数之间的关系.自古以来,人们已将自然数分成各种不同类型.下面是一些熟悉的或不那么熟悉的例子: 奇数1,3,5,7,9,11,- 偶数2,4,6,8,10,- 平方数1,4,9,16,25,36,- 立方数1,8,27,64,125,- 素数2,3,5,7,11,13,17,19,23,29,31,- 合数4,6,8,9,10,12,14,15,16,- 模4余1的数1,5,

判断一个数是质数的优化算法

问题描述 判断一个数是质数的优化算法 判断1000 000 00内的一个数是否是素数,比较优化一点的,i从2到sqrt(i)循环判断,效率不行,希望大神指点. 解决方案 用一个表记录下已经找到的素数,判断更大的数的时候,只要判断2~sqrt(i)范围内素数表上的数就可以了.因为一个数如果可以被一个合数整除,必然可以被由它构成的素数整除. 具体算法http://blog.csdn.net/liukehua123/article/details/5482854 解决方案二: 可以参考以下链接 htt

【转载】Python脚本判断一个数是否为素数的几种方法

     质数又称素数.指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数.素数在数论中有着很重要的地位.比1大但不是素数的数称为合数.1和0既非素数也非合数.质数是与合数相对立的两个概念,二者构成了数论当中最基础的定义之一.基于质数定义的基础之上而建立的问题有很多世界级的难题,如哥德巴赫猜想等.算术基本定理证明每个大于1的正整数都可以写成素数的乘积,并且这种乘积的形式是唯一的.这个定理的重要一点是,将1排斥在素数集合以外.如果1被认为是素数,那么这些严格的阐述就不得不加上

URAL 1132 二次剩余

1132. Square Root Time limit: 1.0 second Memory limit: 64 MB The number x is called a square root of a modulo n (root(a,n)) if x*x = a (mod n). Write the program to find the square root of number a by given modulo n. Input One number K in the first l

蓝桥杯 历届试题 公式求值 (想了很久了,想不明白,才来请教的,麻烦各位了)

问题描述 蓝桥杯 历届试题 公式求值 (想了很久了,想不明白,才来请教的,麻烦各位了) 问题描述 输入n, m, k,输出下面公式的值. 其中C_n^m是组合数,表示在n个人的集合中选出m个人组成一个集合的方案数.组合数的计算公式如下. 输入格式 输入的第一行包含一个整数n:第二行包含一个整数m,第三行包含一个整数k. 输出格式 计算上面公式的值,由于答案非常大,请输出这个值除以999101的余数. 样例输入 3 1 3 样例输出 162 样例输入 20 10 10 样例输出 359316 数据

费马大定理:一部跨越时代的惊险小说

费马大定理本身从提出到证明的过程,就是一部不折不扣的惊险小说. 一个读者,在自己读过的书的空白处留下附注.除了他自己之外,还有谁会关注呢? 但是,法国人费马死后,他在一本<算术>书上所写的注记并没有随之湮没.其长子意识到那些草草的字迹也许有其价值,就用五年时间整理,然后印出一个特殊的<算术>版本,载有他父亲所做的边注,那里面包含了一系列的定理. 在靠近问题8的页边处,费马写着这么几句话: "不可能将一个立方数写成两个立方数之和:或者将一个4次幂写成两个4次幂之和:或者,总

对程序设计初学者谈程序的效率

[摘要]设计高效率的程序是个重要话题.限于基础,初学者往往不得要领.本文试图较通俗地传达算法设计和分析中的一些观点.方法.帮助学生树立算法的概念,注重将来算法理论的学习. 在学习了循环以后,我们可以做程序,解决些大问题了.我想谈谈关于程序执行效率的问题. 评价一个程序的标准中,第一是正确:第二是可读性好,以此使程序易于修改和维护:第三就是效率的问题了,要求程序运行要尽可能快,占用内存空间要尽可能小.关注效率,可以使我们的好程序能在"小设备"上运行,这在移动计算.物联网时代很要紧.还有些