标签 数论 下的文章
- 首页
- 数论
SPOJ FIBONOMIAL - Fibonacci Polynomial
SPOJLuogu分析为了方便，设两个求和号中的部分利用等比数列求和公式计算即可。但是 $5$ 在模 $10^9+7$ 意义下没有二次剩余，所以需要扩域。代码// =================================== // author: M_sea // websi...
CF915G Coprime Arrays
CodeforcesLuogu分析先考虑怎么求 $b_m$ 。考虑每个 $d$ 对每个 $\Delta b$ 的贡献即可，预处理 $n$ 次幂后时间复杂度为 $O(k\log k)$ 。代码// =================================== // author: ...
洛谷1447 [NOI2010]能量采集
Luogu分析智推推的傻逼题 ::paopao:tieba_emotion_25:: 显然答案为线性筛 $\varphi$ ，数论分块计算即可。代码// =================================== // author: M_sea // website: ...
洛谷4619 [SDOI2018]旧试题
LuoguLOJ分析果然是毒瘤人讲毒瘤题... @$\mathsf{\color{black}{x}\color{red}{gzc}}$ 首先要知道显然我们可以 $O(C\log C)$ 预处理出 $f_a,f_b,f_c$ ，然而计算还是 $O(n^3)$ 的。但是注意到 $O(n^3)$ ...
洛谷1829 [国家集训队]Crash的数字表格 / JZPTAB
Luogu分析这里写两种方法，一种是套路，一种是 $\mathsf{\color{black}{x}\color{red}{gzc}}$ 的神仙方法。下文中，设 $n\leq m$ ，$n/m=\left\lfloor\frac{n}{m}\right\rfloor$ 。为了方便，设 $S(n...
洛谷4774 [NOI2018]屠龙勇士
LuoguLOJUOJ分析显然每一条龙用的剑是确定的，可以用 multiset 维护剑的集合，然后每次 upper_bound 出用的剑。设第 $i$ 条龙用的剑的攻击力为 $atk_i$ ，生命值为 $a_i,$ 恢复能力为 $p_i$ ，容易列出方程$x'$ 可以用 exgcd 求解。这样...
CF809E Surprise me!
CodefocesLuogu分析$\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题，报警了...首先要知道$f$ 和 $g$ 都很好转移，同时 $dp$ 也很好转移了。因为 DP 只统计了 $i<j$ 的情况，所以要答案要乘 $2$ ；最后答案...
洛谷2485 [SDOI2011]计算器
Luogu分析数论模板三合一？快速幂板子。exgcd 板子。BSGS 板子。然后注意要开 long long 。代码// =================================== // author: M_sea // website: http://m-sea-blog...
洛谷2150 [NOI2015]寿司晚宴
Luogu重新写一遍 qwq分析先考虑一个 $30$ 分做法。设 $dp_{i,j,k}$ 表示前 $i$ 个数，小 G 选的数的质因子集合为 $j$ ，小 W 选的数的质因子集合为 $k$ 的方案数。转移枚举一下当前的数给谁即可。 $i$ 可以滚动数组滚掉。注意到 $n$ 最多有一个 $&g...
UVA1434 YAPTCHA
UVaLuoguVjudge分析威尔逊定理：$(p-1)!\equiv -1\pmod p\Longleftrightarrow p\text{ 是素数}$ 。考虑如何计算 $\Big\lfloor\frac{(3k+6)!+1}{3k+7}-\big\lfloor\frac{(3k+6)!}...