数论基础讲解东北师范集训队.pdf

搜索

东北师范大学ACM集训队

HappyCoding~

首页acm简介参赛/举办情况校赛成绩短片集锦就业去向相关

←上⼀篇下⼀篇→

数论基础讲解

于2014年8月30日由lightstarlight

数论，顾名思义，是对整数进行研究的理论。是数学学科的一个重要分支，也是ACM竞赛题型中饶有趣味的一个部分。

数论，有人戏称为“素论”。可见对于素数的研究在数论中之大。当然，也有不是对素数操作的算法，在这里我们也将其

划归为数论。

1、整除：

1.1.定义：

若a%b0,则称a能被b整除或b能整除a，记作ba.

1.2.整除的性质：

(1)0可以被任何非0数整除

(2)若ba，则ba

(3)传递性：abbcac.

(4)如果a、b都能被c整除，那么(a+b)或(a-b)也可以被c整除

(5)几个数相乘，如果其中有一个因数能被某一个整除相除，那么它们的积也能被这个数整除。

还有几个略实用的性质：

(1)能被2整除的数，个位上的数都能被2整除

(2)能被4整除的数，个位和十位所组成的两位数能被4整除

(3)能被8整除的数，百位、十位和个位所组成的三位数能被8整除

(4)能被5整除的数，末尾是0或5

(5)能被25整除的数，十位和个位所组成的两位数能被25整除

(6)能被125整除的数，百位、十位和个位所组成的三位数能被125整除

(7)能被3整除的数，各个数位上的数字之和能被3整除

(8)能被9整除的数，各个数位上的数字和能被9整除

1/9

(9)如果一个数既能被2整除又能被3整除，那么这个数能被6整除