洛谷5366 [SNOI2017]遗失的答案
Luogu LOJ 分析 首先特判掉 $G\nmid L$ 的情况。 为了方便，将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数，必须选 $X$，选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。 我们先不管那个必须选 $X$ 的条件，想一想怎么做。 注意到值域只有 $10^8$，即最多只有 $8...
标签 数论 下的文章
- 首页
- 数论
LOJ6704 健身计划
LOJ 分析 设 $f_i$ 表示 $n=i$ 时的答案，容易得到 直接矩阵快速幂即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <a...
CF1220D Alex and Julian
Codeforces 分析 考虑两个数 $a,b$ 要满足什么条件才可以同时留下。 可以发现，$a,b$ 可以构出一个 $0\to a\to \cdots\to\operatorname{lcm}(a,b)\to \operatorname{lcm}(a,b)-b\to\cdots 0$ 的环，这个环的大小是 显然可以根据 $a,b$ 的奇偶性进行讨论： 若 $a,b$ 都为奇数，则上式...
CF1097D Makoto and a Blackboard
Codeforces Luogu 分析 容易想到设 $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...
洛谷5444 [APIO2019]奇怪装置
Luogu LOJ 分析 这个东西显然是有循环节的。 假设 $t_1$ 和 $t_2$ 两时刻 $x,y$ 相等，那么有 那么如果输入的区间中有长度 $\geq$ 最小循环节长度的，直接输出最小循环节长度；否则问题变为区间覆盖，按左端点排序后扫一遍即可。 代码 // =================================== // author: M_sea // we...
CF55D Beautiful numbers
Codeforces Luogu 分析 显然是数位 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}$ ...
SPOJ FIBONOMIAL Fibonacci Polynomial
SPOJ Luogu 分析 为了方便，设 两个求和号中的部分利用等比数列求和公式计算即可。 但是 $5$ 在模 $10^9+7$ 意义下没有二次剩余，所以需要扩域。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ============...
洛谷4619 [SDOI2018]旧试题
Luogu LOJ 分析 首先要知道 显然我们可以 $O(C\log C)$ 预处理出 $f_a,f_b,f_c$ ，然而计算还是 $O(n^3)$ 的。 但是注意到 $O(n^3)$ 的枚举中会出现很多贡献为 $0$ 的情况： $\mu(x),\mu(y),\mu(z)$ 中有 $0$ 。 $\operatorname{lcm}(x,y)>A$ 或 $\operatorname{...
洛谷1829 [国家集训队]Crash的数字表格 / JZPTAB
Luogu 分析 下文中，设 $n\leq m$ ，$n/m=\left\lfloor\frac{n}{m}\right\rfloor$ 。 为了方便，设 $S(n)=\sum_{i=1}^ni=\frac{n(n+1)}{2}$ 。 令 $\mathbf{f}(i)=\frac{1}{i}$，$\mathbf{g}(i)=\mathbf{f}*\mu$ 。 括号内线性筛预处理，然后数论分...
CF809E Surprise me!
Codefoces Luogu 分析 $\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题，报警了... 首先要知道 $f$ 和 $g$ 都很好转移，同时 $dp$ 也很好转移了。 因为 DP 只统计了 $i<j$ 的情况，所以要答案要乘 $2$ ；最后答案记得还要乘上 $\frac{1}{n(n-1)}$ 。 其实这题写起来挺休闲的 代码 ...