数学杂题

[更新中] – 简单的数学题 / 结论题 / 一些套路。

Luogu 4942 – 小凯的数字

题目链接:Luogu 4942

思路:$10^n \equiv 1^n \equiv 1 \pmod{9} $,所以原题的答案就等于$[l + (l+1) + (l + 2) \cdots + (r – 1) + r] \pmod{9}$,即$\frac{(l+r)(r-l+1)}{2}  \pmod{9}$,注意$(l+r)$和$(r – l + 1)$必定一奇一偶。

计蒜客 A1947 – An Olympian Math Problem

题目链接:ICPC 2018 南京网络赛A题

思路:列项,$i \times i ! = (i + 1) i ! – i ! = – i ! + (i + 1) !$。由此$S$化简为$S = (n! – 1) \mod n = n – 1 (n \geq 2)$。

Luogu 1516 – 青蛙的约会

题目链接:Luogu 1516

思路:设时间为$t$,那么题目转化为同于解同余方程$mt+x \equiv nt+y \pmod{L}$,即$L| [(mt+x) – (nt+y) ] \rightarrow L| [(m-n)t – (y – x) ]$,则存在$s$使得$(m-n)t + Ls = y – x$。考虑方程$(m – n) t + Ls = gcd(m-n, L)$的解,可以用扩展欧几里得算法求出一组可行解。如果$gcd(m – n, L) | L$,那么原方程有解,否则无解。有解的时候,通过对$t$累加$\frac{L}{gcd(m – n)}$,调整$t$的值变成最小整数解,再乘以$\frac{y – x}{gcd(m – n)}$得到原方程的解。

LOJ 2605 – 同余方程

题目链接:LOJ 2605

思路:$ax \equiv 1 \pmod{b} \rightarrow ax + by = 1$,考虑$ax+by = d, d = gcd(a,b)$,同Luogu 1516后半部分思路,找最小整数解。这里题目保证解一定存在,实际上是说$d | x$一定成立。

Luogu 3951 – 小凯的疑惑

题目链接:Luogu 3951

思路:求$ax+by=c$有非负整数解的时候最小的$c$。$(a,b)=1$,故$ax+by=1$有解,则$ax+by=c$有解,考虑其通解:

$$ x = x_0 + bt, y = y_0 – at $$

我们可以通过调节$t$来约束$x$在$0 \leq x \leq b – 1$的范围内,此时如果$y \geq 0$则原方程存在非负整数解。如果$y < 0$ 即$y \leq -1$,则不存在,此时

$$ax + by \leq a(b-1) + b \cdot (-1) = ab – a – b$$

所以$c \leq ab – a – b $的时候无没有非负整数解。

考虑$c$的最大值,猜想是否就是$ab-a-b$。反证法:假设$ax+by=ab-a-b$有非负整数解,则$a(x+1)+b(y+1)=ab$,故$a|b(y+1)$,由于$(a,b) = 1$,所以$a|y+1$,则有$a \leq y+1$,同理$b \leq x+1$。所以$a(x+1)+b(y+1) \geq 2ab > ab$,与$a(x+1)+b(y+1)=ab$矛盾,故无解。

综上所述,$c$的最大值为$ab-a-b$。

结论:两个素数$a$和$b$的非负系数线性组合最大不可表示数字为$ab-a-b$。

 

Luogu 4777 – 扩展中国剩余定理

题目链接:Luogu 4777

思路:先考虑两个方程的情况。

$$ x \equiv b_1 \pmod{a_i}, x \equiv b_2 \pmod{a_2} $$

则方程一定可以取一个特解$x=ua_1 + b_1=va_2+b_2$。取$T = [a_1, a_2] $,则可以表示出方程的通解$x=ua_1+b_1+kT=va_2+b_2+kT$,另$S =ua_1 + b_1=va_2+b_2$,则$x \equiv S \pmod{T}$,这样就可以将两个同于方程合并成一个。我们已经知道了$T$的求法,考虑怎么求$S$,已知$a_1$和$b_1$需要知道$u$。

$$ua_1+b_1=va_2+b_2 \Rightarrow (a_1)u + (-a_2)v = b_2 – b_1$$

可以使用扩展欧几里得求解。

Luogu 3868 – 猜数字

题目链接:Luogu 3868

方法一:同Luogu 4777 – 扩展中国剩余定理,合并两个同余方程为一个同于方程。

方法二:利用中国剩余定理的结论,对于同余方程组$x \equiv a_i \pmod{b_i}$,记$m = \prod_{i=1}^{n} b_i$,$M_i = \frac{m}{b_i}$,$t_i$为$M_i$模$b_i$意义下的逆元。那么方程组的解可以表示为$x = (\sum_{i – 1}^{n} a_i M_i t_i) \bmod{m}$。

注意这里的乘法可能会超过long long的范围,可以使用类似快速幂的方法倍增做乘法。

LOJ 110 – 乘法逆元

归纳一下逆元的三种求法:

  • 模素数意义下的逆元$ax \equiv 1 \pmod{p}$,$x = a^{p-2} \bmod{p}$,快速幂求解,$O(\log p)$的时间内求出一个数的逆元
  • 一般情况下$ax \equiv 1 \pmod{p}$可以化成线性方程$ax + py = 1$,使用扩展欧几里得求解,$gcd(a,p)|x$时候逆元存在,$O(\log \min \{a,p \} )$时间内求出一个数的逆元
  • 如果需要求$[1,n]$内所有数字在模$p$意义下的乘法逆元,可以使用线性递推的方法$f(i) = – \lfloor \frac{p}{i} \rfloor \cdot f(p \bmod i) \pmod{p}$,可以在$O(n)$的时间内求出$[1,n]$所有的答案

线性求逆元推导/证明过程:

假设我们要求$i$在模$M$意义下的乘法逆元。首先可以把$M$表示成$M = \lfloor \frac{M}{i} \rfloor \cdot i + (M \bmod i)$,则有

$$\lfloor \frac{M}{i} \rfloor \cdot i + (M \bmod i) \equiv 0 \pmod{M}$$

记$t =\lfloor \frac{M}{i} \rfloor$,$k =M \bmod i$,那么

$$ti+k \equiv 0 \pmod{M}$$

可以推得$-ti \equiv k \pmod{M}$,两边同时乘$i^{-1}k^{-1}$,得到$-tk^{-1} \equiv i^{-1} \pmod{M}$,代入$t$和$k$,假设用$f(x)$表示$x$的逆元,即它也等于$x^{-1}$,那么

$$-\lfloor \frac{M}{i} \rfloor  \cdot f(M \bmod i) \equiv f(i) \pmod{M}$$

证毕。

注意初始化$f(1) = 1 \bmod M$。

LOJ 2034 – 排列计数

题解链接:LOJ 2034 题解

总结:预处理阶乘求组合数。

Codeforces 451A – Game With Sticks

题目链接:Codeforces 451A

思路:$f(x,y)$表示$x$行$y$列的场面下是先手胜还是后手胜。那么$f(x,y) = \overline{f(x-1,y-1)}$,因为去掉一个点相当于去掉了一根横向的直线和一根纵向的直线。

POJ 1354 – Placement of Keys

题目链接:POJ – 1354

思路:假设已经知道$n = i$的答案$f(i)$,考虑$n = i + 1$时新加入的那一个。第$i+1$个不能放在第$i+1$位,那么新加入的这个可以可前面的$i$个当中的任意一个互换,和每个$x \in [1,i]$互换的时候就变成了$n = i$的情况,对答案产生的贡献是$f(i)$,那么么$i$个数字就是$i \cdot f(i)$。故$f(i + 1) = i \cdot f(i)$边界条件$f(3) = 4$。(考虑互换位置是推导错位排序的思想)

51Nod 1058 – N阶乘的长度

题目链接:51Nod 1058

思路:求一个数的位数,$f(x) = \lfloor \log_{10} x \rfloor + 1 $

方法一:

$$\begin{aligned} f(N!)  & = \lfloor \log_{10} N! \rfloor + 1  \\  & =\lfloor \log_{10} N  +\log_{10} (N – 1) + \cdots \log_{10} 1  \rfloor + 1 \end{aligned}$$

 

方法二:利用斯特林公式

$$\lim_{n \to + \infty} = \frac{n!}{\sqrt{2 \pi n} \left( \frac{n}{e} \right) ^ n } = 1$$

所以

$$ n! \approx {\sqrt{2 \pi n } \left( \frac{n}{e} \right) ^ n } $$

根据维基百科斯特林公式的词条:

斯特灵公式是一条用来取n阶乘近似值的数学公式。一般来说,当n很大的时候,n阶乘的计算量十分大,所以斯特灵公式十分好用,而且,即使在n很小的时候,斯特灵公式的取值已经十分准确。

再利用$f(x) = \lfloor \log_{10} x \rfloor + 1 $求解即可。

51Nod 1130 N的阶乘的长度 V2(斯特林近似)中发现$\pi$取$3.1415926$,$e$取$2.718281828$不够精确,更精确地,应当使用acos(-1.0)来定义$\pi$,$e = 2.718281828459$。

51Nod 1118 – 机器人走方格

题目链接:51Nod 1118

思路:从起点到终点一共要走$n+m-2$步,分为$n-1$步和$m-1$步,分别是横着走和竖着走,那么最终答案就是${ n + m – 2 \choose m – 1 } ={ n + m – 2 \choose n – 1 } $,这里组合数中$ n, m \leq 1000 $可以用递推处理,也可以使用乘法逆元。

而我偷懒交了一发Python。

51Nod 1003 – 阶乘后面0的数量

题目链接:51Nod 1003

更详细的思路参考《编程之美》2.2节。

思路:$2 \times 5 = 10$产生一个0,那么我们要考虑$N!$因数中的2和5能配多少对。由于2的数量是大于5的数量的,所以只要考虑5的个数。对于$10^9$的范围,对于每个数求它的因数5的个数再求和会TLE。考虑下面这个式子:

$$Z = \lfloor \frac{N}{5} \rfloor +\lfloor \frac{N}{5^2} \rfloor + \lfloor \frac{N}{5^3} \rfloor + \cdots  $$

$Z$就是$N!$中5的数量,$\lfloor \frac{N}{5} \rfloor$表示不大于$N$的数中5的倍数贡献一个5,$\lfloor \frac{N}{5^2} \rfloor$ 表示不大于$N$中$5^2$的倍数再贡献一个$5$,以此类推。

LOJ 124 – 除数函数求和1

题目链接:LOJ 124

思路:考虑对$d$分类讨论:

$$\sum_{i = 1}^{n} \sigma_{k} (i) = \sum_{i = 1}^{n} \sum_{d|i} d^k = \sum_{d = 1} ^ {n} d^k \lfloor \frac{n}{d} \rfloor   $$

然后直接求和即可,复杂度$O(n \log k)$,$k$为$d$的位数。当然我写的代码在快速幂没有内联之前TLE两个点,内联之后AC,应该有更好的写法,待填坑。

51Nod 1381 – 硬币游戏

题目链接:51Nod 1381

思路:半径为$r$的硬币和直线的交点个数可能是$2r$和$2r+1$,$2r+1$当且仅当圆与直线相切,为小概率事件,在计算期望的时候概率为0,那么$2r$的概率就为1,那么$E = 2r$。

51Nod 1031骨牌覆盖

题目链接:51Nod 1031

思路:$f(i)$表示$2\times i$的答案。考虑每次$i+1$相当于多加了两个方块,假设这两个方块放在最后,如果竖着放,那么前面的$i$列对$f(i+1)$的贡献是$f(i)$,如果横着放,那么后两列都得横着放,前面$i-1$列的贡献是$f(i-1)$,所以$f(i+1) = f(i) + f(i-1)$。

 

说点什么

avatar
50
  Subscribe  
提醒