LOJ6704 健身计划
LOJ分析毒瘤 longge设 $f_i$ 表示 $n=i$ 时的答案，容易得到直接矩阵快速幂即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include &l...
标签 数论 下的文章
- 首页
- 数论
CF839D Winter is here
CodeforcesLuogu分析设 $dp_i$ 表示 $\gcd$ 为 $i$ 的子序列的总长度。考虑容斥，用 $\gcd$ 为 $i$ 的倍数（包括 $i$）的子序列的总长度减去 $\gcd$ 为 $i$ 的倍数（不包括 $i$）的子序列的总长度。先考虑第一部分。设 $s$ 为 $i$ 的倍数的个数，则第一部分的答案为于是就很容易算出 $dp_i$ 了。实现上统计 $i$ 的倍数个数时...
HDU4676 Sum Of Gcd
HDU分析令 $p_{a_i}=i$，则题目要求的是考虑莫队，加入一个数时枚举约数更新贡献即可。时间复杂度 $\mathcal{O}(\text{能过})$。当然你 $\mathcal{O}(\sqrt{n})$ 枚举约数当然是过不了的，可以开一个 vector 存下所有约数。代码// =================================== // author: M_se...
CF1220D Alex and Julian
CodeforcesLuogu洛谷那个翻译有毒吧...题意都讲错了... 然后我想了半天不会做分析考虑两个数 $a,b$ 要满足什么条件才可以同时留下。可以发现，$a,b$ 可以构出一个 $0\to a\to \cdots\to\operatorname{lcm}(a,b)\to \operatorname{lcm}(a,b)-b\to\cdots 0$ 的环，这个环的大小是显然可以根据 $...
CF1097D Makoto and a Blackboard
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$ 的形...
洛谷4562 [JXOI2018]游戏
LuoguLOJ分析我们把 $[l,r]$ 内不是其它任何数的倍数的数称为“关键数”，那么 $t(p)$ 等于 $p$ 中最后一个关键数的位置。考虑如何计算答案。设 $s$ 为 $[l,r]$ 内关键数的数量，那么枚举最后一个关键数的位置，可以得到这个感觉还是比较显然的。那么我们只需要筛法求出 $s$ 然后直接算就好了。代码// ===============================...
洛谷5444 [APIO2019]奇怪装置
LuoguLOJ分析这个东西显然是有循环节的。假设 $t_1$ 和 $t_2$ 两时刻 $x,y$ 相等，那么有那么如果输入的区间中有长度 $\geq$ 最小循环节长度的，直接输出最小循环节长度；否则问题变为区间覆盖，按左端点排序后扫一遍即可。代码// =================================== // author: M_sea // website: h...
洛谷4397 [JLOI2014]聪明的燕姿
Luogu分析你们这是什么输出格式啊，你们真是害人不浅啊你们这个输出格式！若搜索，对于每个 $p_i$ 枚举它的 $c_i$。注意到这里至多有一个 $p_\sqrt{S}$，因此我们只需要枚举 $\sqrt{S}$ 内的质数，再特殊处理剩下的那一个就好了。代码// =================================== // author: M_sea // webs...
洛谷3455 [POI2007]ZAP-Queries
LuoguBZOJ分析线性筛 $\mu$ 的前缀和，然后数论分块计算即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm&g...
CF55D Beautiful numbers
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}$ 是动态变化...