LOJ分析毒瘤 longge设 $f_i$ 表示 $n=i$ 时的答案,容易得到直接矩阵快速幂即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include &l...
CodeforcesLuogu分析设 $dp_i$ 表示 $\gcd$ 为 $i$ 的子序列的总长度。考虑容斥,用 $\gcd$ 为 $i$ 的倍数(包括 $i$)的子序列的总长度减去 $\gcd$ 为 $i$ 的倍数(不包括 $i$)的子序列的总长度。先考虑第一部分。设 $s$ 为 $i$ 的倍数的个数,则第一部分的答案为于是就很容易算出 $dp_i$ 了。实现上统计 $i$ 的倍数个数时...
HDU分析令 $p_{a_i}=i$,则题目要求的是考虑莫队,加入一个数时枚举约数更新贡献即可。时间复杂度 $\mathcal{O}(\text{能过})$。当然你 $\mathcal{O}(\sqrt{n})$ 枚举约数当然是过不了的,可以开一个 vector 存下所有约数。代码// =================================== // author: M_se...
CodeforcesLuogu洛谷那个翻译有毒吧...题意都讲错了... 然后我想了半天不会做分析考虑两个数 $a,b$ 要满足什么条件才可以同时留下。可以发现,$a,b$ 可以构出一个 $0\to a\to \cdots\to\operatorname{lcm}(a,b)\to \operatorname{lcm}(a,b)-b\to\cdots 0$ 的环,这个环的大小是显然可以根据 $...
CodeforcesLuogu分析容易想到设 $dp_{i,j}$ 表示 $j$ 次操作后 $i$ 的期望大小,转移直接枚举约数即可。然而这样子显然是会 T 的...注意到当 $\gcd(i,j)=1$ 时有 $dp_{i\times j,k}=dp_{i,k}\times dp_{j,k}$,因此我们可以将 $n$ 分解为 $p_1\!^{c_1}p_2\!^{c_2}\cdots$ 的形...
LuoguLOJ分析我们把 $[l,r]$ 内不是其它任何数的倍数的数称为“关键数”,那么 $t(p)$ 等于 $p$ 中最后一个关键数的位置。考虑如何计算答案。设 $s$ 为 $[l,r]$ 内关键数的数量,那么枚举最后一个关键数的位置,可以得到这个感觉还是比较显然的。那么我们只需要筛法求出 $s$ 然后直接算就好了。代码// ===============================...
LuoguLOJ分析这个东西显然是有循环节的。假设 $t_1$ 和 $t_2$ 两时刻 $x,y$ 相等,那么有那么如果输入的区间中有长度 $\geq$ 最小循环节长度的,直接输出最小循环节长度;否则问题变为区间覆盖,按左端点排序后扫一遍即可。代码// =================================== // author: M_sea // website: h...
Luogu分析你们这是什么输出格式啊,你们真是害人不浅啊你们这个输出格式!若搜索,对于每个 $p_i$ 枚举它的 $c_i$。注意到这里至多有一个 $p_\sqrt{S}$,因此我们只需要枚举 $\sqrt{S}$ 内的质数,再特殊处理剩下的那一个就好了。代码// =================================== // author: M_sea // webs...
LuoguBZOJ分析线性筛 $\mu$ 的前缀和,然后数论分块计算即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm&g...
CodeforcesLuogu分析显然是数位 DP,但是要想清楚这个条件怎么处理。注意到如果 $a_1|d,a_2|d,\cdots,a_k|d$,那么 $\operatorname{lcm}(a_1,a_2,\cdots,a_l)|d$。因此我们只需要知道这个数对每一位上的数的 $\operatorname{lcm}$ 取模的结果。但是 $\operatorname{lcm}$ 是动态变化...