洛谷5320 [BJOI2019]勘破神机
LuoguLOJ分析显然二合一，先考虑 $m=2$ 的情况。可以知道 $2\times n$ 网格的方案数就是 $f_{n+1}$。为了方便，我们把 $l,r$ 都加上 $1$，那么相当于要求用同样的方法扩域计算即可。代码// ==================================== // author: M_sea // website: https://m-sea...
标签 数论 下的文章
- 首页
- 数论
洛谷6962 [NEERC2017]Knapsack Cryptosystem
LuoguGym分析一个做法是直接 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$ 大时去枚举 $a...
CF582D Number of Binominal Coefficients
CodeforcesLuogu分析首先有一个定理：${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 简要题解
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 怎么办？只剩下一个质因子和剩下两个相同质...