题解

数论

1.基本概念

取模

$a \% b$表示a除以b的余数

取模的性质

$$a\%b = a-b \times \lfloor \frac{a}{b} \rfloor$$ $$(a \% b + b \% c)\% c = (a+b) \% c$$ $$(a \% c )\times(b \% c) \% c = (a\times b) \% c$$

整除

整除通常用$a | b$表示，表示a能整除b，或a是b的约数。

判断

判断用$[n=1]$若$n=1$成立，则值为1，否则为0

求和符号

$$\sum_{beginning}^{ending}{expressions}$$

求和符号的基本性质

当有常数项时，可以提取（加法分配率）

$$\sum_{i=1}^{n}{a \times i} = a\times \sum_{i=1}^{n}{i}$$

常用公式（必须记住）

$$\sum_{i=1}^{n}{i} = \frac{1}{2}n(n+1)$$ $$\sum_{i=1}^{n}{i^2} = \frac{1}{6}n(n+1)(2n+1)$$ $$\sum_{i=1}^{n}{i^3} = \frac{1}{4}n^2(n+1)^2$$

2.整除

设a为非0整数，如果存在一个整数q，使得$b=a \times q$,那么就说b可被a整除，记作 $a|b$,且称b是a的倍数，a是b的约数。 整除具有如下性质：

• 如果$a|b$且$b|c$,则$a|c$
• $a|b$且$a|c$等价于对于任意的整数$x,y$,有$a|(b\times x+c\times y)$
• 设$m \neq 0$,那么$a|b$等价于$(m\times a)|(m\times b)$
• 若$b=q\times d+c$，那么$d|b$的充要条件是$d|c$
• 设整数x,y满足下式：$a\times x+b\times y = 1$,且$a|n$、$b|n$，那么$(a\times b)|n$

3.算数基本定理、欧拉函数

先鸽了，等上课讲