本文主要是介绍acm数学常识入门（给新生），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

模意义（同余）

同余为数论中的重要概念：
一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余。
记作: a ≡ b ( m o d m ) a≡b(mod m) a≡b(modm)或者说 a % m = b a\%m = b a%m=b 。
其中 %就是取模运算符；
对模m同余是整数的一个等价关系。

同余有很多奇妙的性质和玩法（）
首先我们约定：大写字母如 A ≡ a ( m o d p ) A ≡ a(mod p) A≡a(modp)
乘法：

若：AB = C ， 则ab %p= c%p
乘法在模意义下同余仍成立；
A = k 1 ∗ p + a ; A = k1 * p +a; A=k1∗p+a;
B = k 2 ∗ p + b ; B = k2 * p +b; B=k2∗p+b;
C = k 1 ∗ k 2 ∗ p ∗ p + ( a ∗ k 2 + b ∗ k 1 ) ∗ p + a ∗ b C = k1*k2*p*p +(a*k2+b*k1)*p + a*b C=k1∗k2∗p∗p+(a∗k2+b∗k1)∗p+a∗b

加减法同理，手推即可发现仍然不影响同余
除法

在除法中要引进一个定理：
费马小定理：结论为： a P − 1 ≡ 1 ( m o d P ) a^{P-1} ≡ 1 (mod P) aP−1≡1(modP)
即a的p-1次方对模P意义下与1同余；
那么显然 a P − 2 a^{P-2} aP−2就可以看成模意义下的1/a;因为 a ∗ a − 1 = 1 a*a^{-1} = 1 a∗a−1=1;
至此，引入一个方便计算a^b的算法，叫做快速幂，是一个简单实用的 l o g 2 ∗ b log_{2}*{b} log2​∗b 次乘法时间内就能求出来a^b的算法
这是快速幂的解释代码：https://paste.ubuntu.com/p/zJTMWytKFb/

那现在我们要计算b/a在模P意义下等于何数值，显然需要求 b ∗ a P − 2 % P b*a^{P-2}\%P b∗aP−2%P
就能把除法成功变成乘法

这里只说明同余意义下的加减乘除。还有开根号等各种运算都能在模意义下找到解释；

累加累乘，表达式的化简

∑ \sum ∑这是累加符号
∏ \prod ∏这是累乘符号
[ ] [] []这个在式子中出现表示的含义是方括号内容为真，这[**] = 1,否者为假，可以认为是一个真值判别符号；
∣ | ∣这个是整除符号，a|b说明b/a的结果是整数;例如：2|8 , 3|9
A n = 2 n + 3 ; A_n = 2n+3; An​=2n+3;
那么数列A的前n项和 S n S_n Sn​ = ∑ i = 1 n i ∗ 2 + 1 \sum_{i=1}^{n}i*2+1 ∑i=1n​i∗2+1
那么n的阶乘 n ! = ∏ i = 1 n i n! = \prod_{i=1}^ni n!=∏i=1n​i

面对一些表达式，我们看起来要枚举两个数各自从1到n，时间复杂度为n方，但是其实式子化简之后就会变得很简单：以下的n都是1e5:

1

∑ i = 1 n ∑ j = 1 n ∑ k = 1 n i ∗ j ∗ k \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} i*j*k ∑i=1n​∑j=1n​∑k=1n​i∗j∗k
这个式子乍一看是枚举三个元素，求元素之积，只需要固定ij，思考k的变化：显然是ij+ij2+ij3，这是一个等差数列，于是我们快快乐乐地把式子变成：
∑ i = 1 n ∑ j = 1 n i ∗ j ∗ ( n + 1 ) ∗ n 2 \sum_{i=1}^{n}\sum_{j=1}^{n} i*j*\frac{(n+1)*n}{2} ∑i=1n​∑j=1n​i∗j∗2(n+1)∗n​
一看固定i，j的变化也是等差数列，最后i也是等差数列，上面的式子继续化成：
( ( n + 1 ) ∗ n 2 ) 3 (\frac{(n+1)*n}{2})^3 (2(n+1)∗n​)3

这篇关于acm数学常识入门（给新生）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！