数论

洛谷题库 P9118 [春季测试 2023] 幂次

我们有非常易于理解的暴力解法:直接对于 b=3,4b=3,4\cdots,求出所有可以当作底数的 aa,计算 aba^b 后放入数据结构/排序去重;特别处理 b=2b=2 的情况即可。在此不再赘述。

不过,我们注意到若有正整数 xx,满足 x>1,x=a0b0  (a0,b0N)x>1,x=a_0^{b_0}\ \ (a_0,b_0\in \mathbb N),且 a,bN,a0ab\forall a,b\in\mathbb N,a_0\neq a^b(即底数 a0a_0 不可再开根),那么 b,bb0,x=(a0b0/b)b\forall b,b\mid b_0,x=(a_0^{b_0/b})^b。这意味着假如不去重地暴力添加 nb\lfloor\sqrt[b]{n}\rfloor 到答案中,上文中 xx 将被算 {bb00(modb)}|\{b\mid b_0\equiv 0\pmod b\}| 次。

于是这就变成莫反的模板题了:记 g(b)g(b) 表示“能被 aba^b 表出的 xx 之数量”,f(b0)f(b_0) 表示“恰能被 x=a0b0x=a_0^{b_0} 表出,不可被 x=ab,b<b0x=a^b,b<b_0 表出的 xx 的数量”。易得 g(b)=bb0f(b0)g(b)=\sum_{b\mid b_0}f(b_0),故 f(b0)=b0bg(b)μ(b/b0)f(b_0)=\sum_{b_0\mid b}g(b)\mu(b/b_0)。显然,当 b>log2nb>\log_2 n 时仅有 a=1a=1 满足 abna^b\leq n,故我们只需计算 log2n\lfloor\log_2 n\rfloorbb,最后特判 a=1a=1。预处理出 μ\mu 的值,暴力求取反演式,复杂度为 O(log2n)\operatorname{O}(\log^2 n)


其实并不需要这么麻烦。我们根本不需要反演:根据 g(b)=bb0f(b0)g(b)=\sum_{b\mid b_0}f(b_0),假若 b0,b0>b,f(b0)\forall b_0,b_0>b,f(b_0) 都已经计算完成,那么我们直接得到 f(b)=g(b)bb0,b0>bf(b0)f(b)=g(b)-\sum_{b\mid b_0,b_0>b}f(b_0)。由 bb 从大往小计算即可,复杂度相同。

More
  • 2023年3月10日

近一个月来第一次赛时通过一道题。真是可喜可贺。

A – 单调

一开始以为与网络流相关;后来考虑 DP;结果是个贪心或者乱搞。

题意简述

给定长为 n  (n105)\newcommand\bigO{\operatorname{O}}n\ \ (n\leq 10^5) 的序列 ai,ai{1,2,3}\langle a_i\rangle,a_i\in\{1,2,3\}。匹配尽可能多的子序列,每个子序列均为 1,2,3\langle 1,2,3\rangle3,2,1\langle 3,2,1\rangle,且一个位置最多被一个子序列占用。求最大匹配数。 (更多…)

More
  • 2023年2月9日

AtCoder Regular Contest 148 D – mod M Game

鲁莽的尝试?

一个非常显然的 Bob 的必胜局面是:对于任意 x{0,1,,M1}x\in \{0,1,\cdots,M-1\},在这 2N2N 个数中的出现次数均为偶数。由此 Bob 可以选择与 Alice 上一轮选的相同的数而获胜。

那……其他局面就一定是 Alice 必胜么?

我们只依靠该结论交一份代码。不出意料,没有通过。不过它只错了两成的测点!看来大体方向是正确的。

正解

(更多…)

More
  • 2022年9月12日

昨晚参与AtCoder ABC 236时认为G题似乎可做,直到看到数据范围才发现事情没有那么简单

由于最近学习离线数据结构,又见识过一道题意接近的题目,故想到整体二分,二分每一个节点第一次能恰好经过LL条边到达的时间,然后考虑DP求解。设计状态f(i,x)f(i, x)表示在该图上经过恰好ii次转移能否到达点xx。但很快发现每一次二分时均要重新在图上运行DP,时间复杂度无法承受。况且DP递推转移的次数LL高达10910^9,甚至不可能是线性的复杂度。

今天查看题解,发现有几个重要的,从未考虑过的trick:

  1. 既然要求能够经恰好LL次转移到达的最早的时间点,则我们将每条边的边权ww设为其加入图中的时间,则可以转化成恰有LL条边的最小瓶颈路
  2. 发现LL很大,所以考虑通过矩阵乘法加速递推,也即所谓倍增优化DP的一种。

(更多…)

More
  • 2022年1月24日