Throne

记录一下 $blog$ 创建的大体过程：

扩展欧几里得：

对于任意整数 a,b ，求解 ax+by=m

由裴蜀定理可知 ax+by=m 一定有解的充要条件为 gcd(a,b)|m

所以对于解一般的 ax+by=m 不定方程，我们可以先证明ax+by=gcd(a,b),在扩展到一般域

假设一组解为 x1,y1 即ax1+by1=m:

因为gcd(a,b)=gcd(b,a%b) 即 bx2+(a%b)y2=ax1+by1;

其中 a%b=a-b*[a/b] 即 bx2+(a-b*[a/b])y2=ax1+by1

系数对称后可得：x1=y2,y1=x2-[a/b]y2 ;

我们考虑到在gcd(a,b)递归的最终结果为 b|a，则此时ax+b*0=gcd(a,0)=a ,x=1,y=0;

从此时往前递归并借用我们得到的x1,x2,y1,y2 的关系可得最终x1,y1

对于求逆元 ax_= 1(mod m)

即 ax+my =1 与上面同理可得解

2021CCPC桂林 E Buy and Delete

题目：

爱丽丝和鲍勃正在有向图 $G$上玩游戏。在 $G$ 中有 $n$ 个顶点，标记为 $1,2,\dots,n$ 。最初， $G$ 中没有边。爱丽丝会先从商店直接购买一些边，然后将它们添加到 $G$ 中。之后，鲍勃需要删除边，直到 $G$ 中没有边为止。在一轮删除中，鲍勃可以从 $G$ 中删除一个边子集 $S$ ，这样当只保留 $S$ 中的边时，图就是非循环的。请注意，爱丽丝可以什么也不买，在这种情况下，删除回合数为 $0$ 。

商店中有 $m$ 条边。爱丽丝有 $c$美元，因此她要购买的边的总价不应超过 $c$ 。爱丽丝希望最大化删除回合数，而鲍勃希望最小化删除回合数。爱丽丝和鲍勃都将以最优方式下棋。请编写一个程序来预测删除回合数。

Problem - B - Martian Sunrise贪心

Problem - A - Find a Number同余最短路/建图

题目：E-魔法之森的蘑菇

题目描述：

给你一张图，起点为$S$终点为$T$，起初任意选择前进方向，除非遇到 $*$，否则不能更改方向，遇到 $*$ 可以选择朝向除返回刚刚位置的其他方向，# 为障碍物，$.$ 为普通路径，求 $S$ $-$ $>T$ 最短距离。