danihao123's Blog

先去考虑两个变量的sgcd怎么求……我们先求出他们的gcd，然后在除掉一个最小的质因子即可。

那么我们先把$a_1$分解质因数，然后所有数和它求一个gcd，然后去去掉一个尽可能小的质因子。注意到一个数$p$的质因子数量是$O(\log p)$级别的，所以每一个数找到要除的那个最小的质因子只需要$O(\log a_1)$的时间。

代码：

当年在考场上一点反演都不会啊啊啊啊啊啊

这题虽然牵扯到了对积的反演，但其实也不是很难。先让我们大力推导一波（逃

考虑枚举柿子中的$f[(i, j)]$中的最大公约数（设为$k$），然后式子变成了（这里不妨偷个懒，钦定$n\leq m$）：

$$\prod_{k = 1}^n f[k]^{\sum_{i = 1}^n \sum_{j = 1}^m\:[(i, j) = k]}$$

然后发现上面那个指数就是Problem b的式子，显然可化为$\sum_{d = 1}^n \mu(d) \lfloor\frac{n}{kd}\rfloor \lfloor\frac{m}{kd}\rfloor$。然后似乎化简没有余地了，但是根据直觉，我们可以钦定$T = kd$，然后枚举$T$。

然后柿子变成了：

$$\prod_{T = 1}^n (\prod_{k\mid T} f[k]^{\mu(\tfrac{T}{k})})^{\lfloor\tfrac{n}{T}\rfloor \lfloor\tfrac{m}{T}\rfloor}$$

柿子中的$\prod_{k\mid T} f[k]^{\mu(\tfrac{T}{k})}$是一个类似狄利克雷卷积的东西（取完对数就是了），可以枚举约数预处理。并且这个东西很不错的一点就是上面的指数是莫比乌斯函数，可以取到的值只有那三种，不需要快速幂。

然后剩下的部分就和通常的反演题一般无二了……

代码（卡线过的蒟蒻……求轻喷……但我在LOJ上跑的还挺快的）：

终于调过去了……（然而不就是道NTT+生成函数水题吗至于调半天）

首先积非常的恶心，考虑转成和。这个事需要求指标的……求指标的话枚举原根的若干次幂即可（恰好$m$是素数一定有原根……），判断原根用比较大力的手段即可（我搞了一个$O(n\sqrt{n}logn)$的……求轻喷）。

然后这题还算比较简单吧……用生成函数表示原来的集合，然后$n$次幂就可以了。

注意那事个循环卷积……所以要开两倍然后每次乘完了再把右半部分搞过去。

代码：

开个坑，记录一些和反演以及狄利克雷卷积的东西。

首先积性函数、狄利克雷卷积等基本概念不写了，就讲讲性质吧。

有几个一定要记住的东西：

$$\mu \ast 1 = e$$

$$\varphi \ast 1 = id$$

$$\mu \ast id = \varphi$$

这几个在推式子的过程中都有很大的作用，务必要记住。

所谓莫比乌斯反演，其实就是：

$$F = f \ast 1\Leftrightarrow f = F \ast \mu$$

（谜之音：其实很多所谓“反演题”都没用到这俩性质啊……）

关于莫比乌斯函数本身，还有一个好康的性质：

$$(\mu\ast 1)(k) = \sum_{i = 0}^k (-1)^i C_k^i$$

这个题啊……亦可赛艇！

答案是。原因很简单，把分成长度为的若干段，除去第一段外每一段中与互质的数肯定满足（否则，和就会有大于一的公因子了)。所以说每一段内与互质的数都有个。

麻烦好像就在于求一个阶乘的欧拉函数。考虑一个新乘上的数能给答案带来的贡献——如果这个数是合数，它的所有因子在前面都有了，只能把他自己贡献出来；如果这个数是质数（假设为），出了贡献自己以外还会贡献一个，最后乘起来就是贡献了。筛一遍素数再递推一下就好辣~

并且……可能非常大，所以说除去那块要用逆元做。

（顺便说下阶乘也要递推）

代码：

论如何把数论乱搞和图论乱搞出在一起……

这个题由于要求，所以不能gcd乱搞。我们可以先取的最小值（忽略为0的情况，为啥取最小值待会再说），对方程两边模。然后对于任何能使某个同余方程成立的，将其中所有同时加任意个，同余方程都成立。

取模后，，所以说只要对于中的每个数找出最小的一组合法解即能推出其他解（所以说，剩余系越少效率越高，这也就要求取的要小）。不过这个最小的一组合法解怎么找？

我们先找出任意一个合法（比如说0吧），然后尝试加上，就可以推出其他的最小解。这个应用当然是需要最短路辣。

求出来的最短路，表示的是取最小解时的。这样的话就可以推出某个前缀区间中合法的个数（能加多少，就有多少个，注意不要忽略加0个的情况），并且答案符合区间减法，最后做差分即可。

注意忽略的情况（相当于不存在）。

代码：

这个题啊……有规律可循。

我们可以发现，关于答案有如下规律：

然后筛法求欧拉函数即可（我听说神犇们都用了杜教筛哎）

代码：

这个问题看似无从下手。

我们可以先取，然后你就发现你似乎要解，而且还要求最小？你想到了什么？扩展欧几里得？对头！

由扩欧推广可得答案就是所有数的最大公约数。

代码：

狐狸的三种操作的实质是除二，除三，除五。由此我们可以猜想在最优策略下，两块蛋糕最后的重量应该是。然后试除即可。

（大胆猜想，不用证明）

代码：

很经典的问题了吧……然而现在才A……

应注意，然而和都可表示为的乘积，问题就好思考多了。答案就是的质因子的子集数（同一种质因子不能同时分配到P与Q中，否则gcd(P,Q)会不等于x）。

注意有可能无解！

代码：