数学杂题

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

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)$必定一奇一偶。

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$。(考虑互换位置是推导错位排序的思想)

 

说点什么

avatar
50
  Subscribe  
提醒