Codeforces Round #614 简要题解
Div1Div2从一月份一直咕到现在的一场比赛 /kelConneR and the A.R.C. Markland-N暴力往两边找即可。代码JOE is on TV!显然每次淘汰掉刚好一个人是最好的。答案即为 $\sum_{i=1}^n\frac{1}{i}$。代码NEKO's Maze Game维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即可。代码Aroma's...
标签 数论 下的文章
- 首页
- 数论
AtCoder Regular Contest 080 简要题解
比赛地址4-adjacent我们把所有数分成 $3$ 类：$4$ 的倍数、不是 $4$ 的倍数但是是 $2$ 的倍数、奇数。那么肯定是第三种和第一种交错排，在最后放第二种最好。直接判一下第一种的数量是否 $\geq$ 最后一种的数量即可。当没有第二种数时最后还可以放一个第三种数，此时应该是第一种的数量 $+1\geq$ 最后一种的数量。代码Grid Coloring蛇形填上每种颜色即可。代码...
AtCoder Regular Contest 067 简要题解
比赛地址Factors of Factorial直接把 $1\sim n$ 分解质因数即可。代码Walk and Teleport显然从左往右走是最优的，相邻两个选更小的方式即可。代码Grouping设 $dp_{i,j}$ 表示 $i$ 个人分成若干个人数 $\leq j$ 的组的方案数。转移时枚举人数 $=j$ 的组数 $k$，那么首先要在 $n-i+jk$ 个人中选出 $jk$ 个，然...
CF1174E Ehab and the Expected GCD Problem
CodeforcesLuogu分析根据一些小学奥数知识可以知道第一个数应该是 $2^x3^y$ 的形式，而且 $y\in\{0,1\}$ ，因为 $>3$ 的质因子我们换成 $2^k$ 更优，$3^2$ 换成 $2^3$ 更优。为了方便设 $m=\lfloor\log_2 n\rfloor$。考虑 DP。设 $dp_{i,x,y}$ 表示前 $i$ 个数，当前的 $\gcd$ 是 $2...
洛谷6271 [湖北省队互测2014]一个人的数论
Luogu分析先莫比乌斯反演一下后面那个东西是 $(\mu\cdot \mathbf{id})*\mathbf{id}$，显然是积性函数，所以我们可以对于每个质因子单独计算后乘起来。而对于每个质因子显然只有 $x=1$ 和 $x=p$ 时 $\mu(x)$ 不为 $0$，所以只要算两项即可。至于 $f_i$，可以求拉格朗日插值公式中每项系数求出，也可以直接高斯消元。代码// ========...
洛谷6730 [WC2020]猜数游戏
LuoguLOJ分析先简单介绍一下阶。设 $\gcd(a,p)=1$，则满足 $a^x\equiv 1\pmod p$ 的最小正整数 $x$ 被称为 $a$ 在模 $p$ 意义下的阶，记做 $\operatorname{ord}_pa=x$阶有这样一些性质（这里没有证明，可以自行查找相关资料）：$\operatorname{ord}_p a|\varphi(p)$。于是我们可以枚举 $\va...
洛谷3499 [POI2010]NAJ-Divine Divisor
LuoguLOJ分析先筛出 $10^6$ 以内的质数，然后把 $a_i$ 除掉这些质数，这样子每个 $a_i$ 至多剩下两个质因子。可以直接 Pollard-Rho 求出剩下的质因子。这样子第一问的答案即为最多的质因子出现次数，第二问的答案即为 $2$ 的出现次数等于第一问答案的质因子个数次方减 $1$，写个高精度即可。不想写 Pollard-Rho 怎么办？只剩下一个质因子和剩下两个相同质...
POI2011 简要题解
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$，则一定存在一段和为 $w-2$，...
51nod1355 斐波那契的最小公倍数
51nodLOJ分析为了方便，下面简记 $f_S$ 为 $f_{a_1},f_{a_2},\cdots,f_{a_k}$，其中 $S=\{a_1,a_2,\cdots,a_k\}$。考虑一个经典容斥从小到大枚举倍数算贡献即可。实现得好的话时间复杂度是 $\mathcal{O}(n\log n)$ 的。代码// ==================================== // ...
洛谷3700 [CQOI2017]小Q的表格
LuoguLOJ分析可以发现这两条规则长得很像更相减损术，推一推可以得到最后那一步可以考虑实际意义，证明就不写了（如果没有修改的话就可以预处理 $i^2\varphi(i)$ 的前缀和然后数论分块计算了。然而现在还有若干次对于 $f(d,d)$ 的修改，可以想到用一个数据结构来维护。思考一下，我们在数论分块时需要进行 $\mathcal{O}(Q)$ 次修改和求 $\mathcal{O}(Q...