数学相关的一些内容。

扩展欧几里得

好久没碰数论了，感觉自己的基础挂得一塌糊涂，复习一下这玩意吧。

希望求得 $ax+by=c$，先同时除以 gcd 化成 $ax+by=1$ 的形式。然后呢用欧几里得的思想，假设我们已经求得了 $(b,a\%b)$ 的答案，即已知：$x_0b+y_0a\%b=1$，也就是说：

$x_0b+y_0(a-b\lfloor\frac{a}{b}\rfloor)=1\\ x_0b+y_0a-y_0b\lfloor\frac{a}{b}\rfloor=1\\ (x_0-y_0\lfloor\frac{a}{b}\rfloor)b+y_0a=1$

所以答案就变成了 $(y_0,x_0-\lfloor\frac{a}{b}\rfloor y_0)$。有个结论是这样求出来的特解保证了 $|x|$ 值最小，这就从侧面保证了 $|x|+|y|$ 最小。当然我们希望的特解应该是：$x_0=x\times\frac{c}{g},y_0=y\times\frac{c}{g}$。另外，可以求出通解如下：

$\begin{cases} x=x_0+k\times\frac{b}{g}\\ y=y_0-k\times\frac{a}{g} \end{cases}$

板子：

struct node{int x,y,g;};
inline node exgcd(int a,int b){
	if(b==0)return (node){1,0,a};
	node an=exgcd(b,a%b);
	return (node){an.y,an.x-a/b*an.y,an.g};
}

尽管结果不会爆 int，但是在后面的运算中很有可能会用到更大的数，所以在这种题目中能开 long long 就开，总是没错的。板子。

P3518：有一个结论是说，假如 $x$ 是密码，那么 $\forall t,\text{gcd}(x,n)|t$ 都应该是密码，因为它们都可以由 $x$ 硬凑出来。设密码集合为 $S$，不正确的密码集合为 $R$，所以考虑枚举 $\text{gcd}S_i$，令为 $g$，那么需要满足的是 $\forall i,g∤R_i$。在此基础上，由于希望可能的密码最多，那么所有 $g$ 的倍数都应该利用上，也就是说此时的答案是 $\lfloor\frac{n}{g}\rfloor$。所以就是要求最小的 $g$。暴力枚举并判断是不行的，可以考虑从大到小枚举 $\text{gcd}(n,m)$ 的因数，如果当前因数在 $R$ 之中，那么说明这个因数的因数都是不合法的，递推地记录一下即可。有几个小的细节，一个是哈希判断的过程中可以让大于 $10^7$ 以 $\frac{n}{k}$ 的形式存储，这样一来就不需要 map 了。然后就是找质因数的时候一定是大于一（维生素B）。