标签 数论 下的文章
- 首页
- 数论
洛谷5437 【XR-2】约定
Luogu分析完全图的生成树个数为 $n^{n-2}$ ，每条边会出现 $2n^{n-3}$ 次。容易得到答案为考虑怎么计算 $\displaystyle\sum_{i=n+1}^{2n-1}i^k$ 。可以发现 $i^k$ 是完全积性函数，直接线性筛后求前缀和即可。整理一下思路：首先线性筛求...
洛谷5401 [CTS2019]珍珠
LuoguLOJ分析laofu 出的神仙数数题。感谢小粉兔的题解。另外有问题请评论指出。首先题目要求的其实就是方案数。设 $cnt_i$ 表示颜色为 $i$ 的珍珠的数量，那么如果一组方案合法的话会有显然也是一个卷积的形式。于是只需要构造多项式求出 $f_i$ ，再构造多项式求出 $g_i$ ...
CF510E Fox And Dinner
CodeforcesLuogu分析显然每个环一定是奇偶相邻的。考虑这样的网络流模型：源点向每个偶数连容量为 $2$ 的边，代表可以和两个奇数相邻。每个奇数向汇点连容量为 $2$ 的边，意义和上面类似。对于一个偶数 $u$ 和一个奇数 $v$ ，如果 $u+v$ 是质数，那么从 $u$ 向 $v...
CF468C Hack It!
CodeforcesLuogu分析神仙构造题？首先可以发现，当 $x<10^{18}$ 时有这样一个关系式也就是说，当 $[l,r]$ 从 $[1,10^{18}]$ 变成 $[x+1,x+10^{18}]$ 时，$\sum\limits_{i=l}^rf(i)$ 增加了 $x$ 。设 ...
洛谷3747 [六省联考2017]相逢是问候
LuoguLOJ分析扩展欧拉定理：可以发现 $c^{c^{c^{c^\cdots}}}$ 至多 $\log$ 层后指数的模数就会变成 $1$ ，于是可以 $O(\log n)$ 计算这个东西。于是修改直接暴力修改到叶子节点，如果修改次数已经超过最大值了就不用改直接返回。具体的，稍微修改一下快速...
洛谷5451 [THUPC2018]密码学第三次小作业
LuoguLOJ分析一道不错的数论题。因为 $e_1\perp e_2$ ，所以会存在一对数 $s,t$ ，满足 $e_1s+e_2t=1$ 。我们要求的是 $m\bmod N$ 。我们可以对这个式子做一些变形：于是只要求出 $s$ 和 $t$ 即可。因为 $e_1s+e_2t=1$ ，所以可...
TJOI2018简要题解
数学计算因为模数不是质数，所以并不能直接乘个逆元还原回去。事实上维护一棵线段树，每个位置表示该时间乘的值，每次修改直接修改对应位置上的数，查询就输出所有数的乘积即可。代码智力竞赛读进来的时候先把 $n$ 加个 $1$ 。那么就相当于可以用至多 $n$ 条链覆盖 DAG，求未被覆盖的点的点权最小...
CQOI2018简要题解
破解D-H协议$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$ 直接上 $\mathrm{BSGS}$ 求出 $a$ 和 $b$ ，然后答案就是 $g^{ab}\bmod P$ 。代码社交网络【模板】有向图矩阵...
洛谷4495 [HAOI2018]奇怪的背包
LuoguLOJ分析神奇的数学题...先来考虑 $n=1$ 的情况，可以发现所有能取到的体积为 $k\cdot\gcd(v,P)$ 。于是我们可以直接把体积设成 $\gcd(v,P)$ 。这样子所有体积都是 $P$ 的因数了。考虑预处理出 $P$ 的所有因数，然后求出每种因数在体积中 的出现次...
洛谷4707 重返现世
Luogu分析首先你要会 $\text{kth-max}$ 容斥：$\displaystyle\text{kth-max}(S)=\sum_{T\subseteq S}(-1)^{|T|-k}{|T|-1\choose k-1}\min(T)$ 。当然它也可以扩展到期望：$\displayst...