洛谷3934 [Ynoi2016]炸脖龙I
Luogu分析这种题显然要用扩展欧拉定理先考虑没有修改的情况，我们只需要像其它扩展欧拉定理题一样递归下去即可。显然只会递归 $\mathcal{O}(\log p)$ 层，所以复杂度是对的。现在考虑这个修改。我们实际上只需要知道每个位置的值，因此用树状数组实现区间修改、单点查询即可。$\varphi(p)$ 的值显然不能在递归时 $\mathcal{O}(\sqrt{p})$ 求，但是 $p...
标签 数论 下的文章
- 首页
- 数论
洛谷3768 简单的数学题
Luogu分析这样就很好杜教筛了。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define fi...
洛谷4774 [NOI2018]屠龙勇士
LuoguLOJ分析显然用来打每条龙的剑是确定的，可以用 std::multiset 预处理出来。假设打第 $i$ 条龙的剑的攻击力为 $atk_i$。那么如果一个 $x$ 满足条件，则应有这样子就可以直接 exCRT 了。需要注意的是 $a_i\leq 10^{12}$，所以需要写慢速乘。代码// author: M_sea // website: https://m-sea-bl...
CF1285F Classical?
CodeforcesLuogu分析下文中的 $A$ 为 $\max_{i=1}^n\{a_i\}$。考虑枚举答案的 $\gcd$，问题变为求满足 $\gcd(x,y)=g$ 的 $x,y$ 中 $x\times y$ 的最大值。可以考虑贪心。我们先把所有满足为 $g$ 的倍数的数拿出来并从大到小排序，然后依次扫描，同时开一个栈来维护。对于每个数，我们需要判断栈中有没有与它互质的数，假设有 $...
洛谷5366 [SNOI2017]遗失的答案
LuoguLOJ分析首先特判掉 $G\nmid L$ 的情况。为了方便，将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数，必须选 $X$，选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。我们先不管那个必须选 $X$ 的条件，想一想怎么做。注意到值域只有 $10^8$，即最多只有 $8$ 个质因子...
CF1292D Chaotic V.
CodeforcesLuogu分析显然可以将 $k_i$ 相同的点放在一起处理，则点数变为 $5000$ 级别。考虑如何从 $1$ 走到 $n!$。将 $n!$ 质因数分解并把所有质因数从大到小排序，然后依次乘过去即可。既然要计算树的重心，考虑从 $1$ 开始走，每次向 $size$ 最大的子树移动，直到 $maxsize\leq \frac{n}{2}$。现在的问题是如何计算每个点在哪颗子...
51nod1678 lyk与gcd
51nod分析于是只要对于每个 $d$ 暴力维护 $\sum_{d|i}a_i$ 即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <bits...
AtCoder Grand Contest 003 简要题解
比赛地址Wanna go back home如果 E 和 W 仅存在一个，或者 N 和 S 仅存在一个，则一定无法回到原点，否则一定可以回到原点。代码Simplified mahjong直接扫一遍，能凑就凑即可。正确性显然。代码BBuBBBlesort!注意到使用操作 2 后不改变元素下标的奇偶性，而每个元素应该还原到的下标是已知的，因此我们可以统计出有多少个元素始末位置奇偶性不同，记为 $...
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$ 的倍数个数时...