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

标签 扩展欧几里得算法 下的文章

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...
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...
September 26, 2019

欧几里得算法&扩展欧几里得算法

欧几里得算法一、欧几里得(Euclid)算法又称辗转相除法,用于求两数最大公约数。$$(a,b)=(b,a\%b)$$代码:int gcd(int a,int b){ return b?gcd(b,a%b):a; }二、扩展欧几里得(Euclid)算法用于求解方程 $$ax+by=(a,b)$$ 的所有整数解 $(x,y)$ 。考虑 $$(a,b)=(b,a\%b)$$$\becau...