Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

$\gcd$ 是出现在数论而又披着同余的外衣的唯一的函数。

因为关于 $\gcd$ 的东西实际上非常多非常杂,写一个博客记录一下。

而且数论里面基本上是个东西就离不开 $\gcd$ 所以这也是个非常重要的东西。

阅读全文 »

BSGS (北上广深) 算法,用来解决一类 $a ^ x\equiv b \pmod p$ (即离散对数) 的问题。

阅读全文 »

CF gym 102012 J

给出一张有向无环图,每个点上存储了一个具有特定重量和价值的宝石,经过一个点时必须拿取上面的宝石。

对于每个点求出:

禁止经过这个点时,从起点走到终点,且路径上所有宝石重量之和除以 $m$ 的余数为 $k$ 时,所能得到的最大收益。

$n,m \leq 200000$

阅读全文 »

P3354 [IOI2005]Riv 河流

Byteland 国,有 $n$ 个伐木的村庄,这些村庄都座落在河边。目前在 Bytetown,有一个巨大的伐木场,它处理着全国砍下的所有木料。木料被砍下后,顺着河流而被运到 Bytetown 的伐木场。

Byteland 的国王决定,为了减少运输木料的费用,再额外地建造 $k$ 个伐木场。这 $k$ 个伐木场将被建在其他村庄里。这些伐木场建造后,木料就不用都被送到 Bytetown 了,它们可以在运输过程中第一个碰到的新伐木场被处理。显然,如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。

注:所有的河流都不会分叉,形成一棵树,根结点是 Bytetown。

国王的大臣计算出了每个村子每年要产多少木料,你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为:每一吨木料每千米 $1$ 分钱。

$2\le n\le 100$,$1\le k\le \min(n,50)$

阅读全文 »