标签 数论 下的文章
- 首页
- 数论
洛谷5330 [SNOI2019]数论
Luogu LOJ 分析 考虑枚举一个 $A_i$，则我们需要计算 发现 $(Px+A_i)\bmod Q$ 有长度为 $\frac{Q}{\gcd(P,Q)}$ 的循环节，因此我们可以暴力求出循环节，然后计算。这样子是 $\mathcal{O}\left(\frac{nQ}{\gcd(P,Q)}\right)$ 的。 注意到模 $\gcd(P,Q)$ 意义下相等的 $A_i$ 循环节内的...
洛谷5320 [BJOI2019]勘破神机
Luogu LOJ 分析 显然二合一，先考虑 $m=2$ 的情况。 可以知道 $2\times n$ 网格的方案数就是 $f_{n+1}$。为了方便，我们把 $l,r$ 都加上 $1$，那么相当于要求 用同样的方法扩域计算即可。 代码 // ==================================== // author: M_sea // website: https...
洛谷6962 [NEERC2017]Knapsack Cryptosystem
Luogu Gym 分析 一个做法是直接 meet in the middle，复杂度 $\mathcal{O}(2^{n/2})$，并不能过 $n\leq 64$。 但是题目中还有一个奇妙的性质 $a_i > \sum_{j=1}^{i-1} a_j$，套用得到 $a_1<2^{65-n}$。 发现随着 $n$ 增大 $a_i$ 的取值范围逐渐减小，这启发我们在 $n$ 大时去...
CF582D Number of Binominal Coefficients
Codeforces Luogu 分析 首先有一个定理： ${a+b\choose a}$ 质因数分解后 $p$ 的幂次等于 $p$ 进制下 $a+b$ 的进位次数。 于是可以把 $A$ 转成 $p$ 进制，然后考虑数位 DP。设 $dp_{i,j,0/1,0/1}$ 表示前 $i$ 位，进位 $j$ 次，第 $i-1$ 位是否向第 $i$ 位进位，$a+b$ 是否顶着 $A$ 的上界的...
Codeforces Round #614 简要题解
Div1 Div2 从一月份一直咕到现在的一场比赛 /kel ConneR and the A.R.C. Markland-N 暴力往两边找即可。 代码 JOE is on TV! 显然每次淘汰掉刚好一个人是最好的。 答案即为 $\sum_{i=1}^n\frac{1}{i}$。 代码 NEKO's Maze Game 维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即...
CF1174E Ehab and the Expected GCD Problem
Codeforces Luogu 分析 根据一些小学奥数知识可以知道第一个数应该是 $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$ ...
洛谷6271 [湖北省队互测2014]一个人的数论
Luogu 分析 先莫比乌斯反演一下 后面那个东西是 $(\mu\cdot \mathbf{id})*\mathbf{id}$，显然是积性函数，所以我们可以对于每个质因子单独计算后乘起来。而对于每个质因子显然只有 $x=1$ 和 $x=p$ 时 $\mu(x)$ 不为 $0$，所以只要算两项即可。 至于 $f_i$，可以求拉格朗日插值公式中每项系数求出，也可以直接高斯消元。 代码 // =...
洛谷6730 [WC2020]猜数游戏
Luogu LOJ 分析 先简单介绍一下阶。设 $\gcd(a,p)=1$，则满足 $a^x\equiv 1\pmod p$ 的最小正整数 $x$ 被称为 $a$ 在模 $p$ 意义下的阶，记做 $\operatorname{ord}_pa=x$ 阶有这样一些性质（这里没有证明，可以自行查找相关资料）： $\operatorname{ord}_p a|\varphi(p)$。于是我们可以枚...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...