夢に僕らで帆を張って
来るべき日のために夜を超え

标签 乘法逆元 下的文章

October 29, 2019

洛谷P5142 区间方差

题意给出一个数列,$2$种操作单点修改询问区间方差以上操作在$\bmod \ 10^9+7$意义下数据范围:$n,m \le 100000$题解首先方差$$\sigma^2 =\frac{1}{n} \sum_{i=1}^n (x_i-\bar{x})^2$$其中$$\bar{x}=\frac{1}{n} \sum_{i=1}^n x_i$$不满足区间和性质,将其拆开$$ \begin{al...
October 21, 2019

CF1228E Another Filling the Grid

题意一个$n \times n$的矩形,每个格子里可以填$[1,k]$内的整数,求保证每行每列的最小值为$1$的方案数数据范围:$1 \le n \le 250,1 \le k \le 10^9$题解直接计算难以解决,考虑容斥原理枚举有$i$行$j$列的最小值$> 1$,选择方案有$$\sum_{i=0}^n \sum_{j=0}^n (-1)^{i+j} C_n^i C_n^j$$乘...
October 14, 2019

CF1244C The Football Season

题意求解$$ \left\{ \begin{aligned} & wx+dy=p \\ & x+y \le n \\ & x,y\ge 0 \end{aligned} \right. $$的一组解$(x,y)$数据范围:$2 \le n \le 10^{12},1 \le p \le 10^{17},1 \le d < w...
October 12, 2019

洛谷P2613 有理数取余

题意求$c=\frac{a}{b} \bmod 19260817$的值数据范围:$0 \le a,b \le 10^{10001}$题解$$ \begin{aligned} \frac{a}{b} &= a \cdot b^{-1} \\ & \equiv (a \bmod p) \cdot (b^{-1} \bmod p) \end{aligned} $$转化为$a \ti...
September 26, 2019

乘法逆元

乘法逆元一、逆元的定义若 $a \cdot x \equiv 1 \ (\bmod \ p)$ 且 $(a,p)=1$ ,则称 $a$ 关于模 $p$ 的乘法逆元为 $x$ ,记为 $a^{-1}$ 。二、逆元的求法1.费马(Fermat)小定理若 $p$ 为素数,且 $(a,p)=1$ ,则有 $a^{p-1} \equiv 1 \ (\bmod \ p)$ 。由费马小定理 $$a \cd...