标签: 数论

3 篇文章

容斥原理与广义容斥原理
前言 这是我在中考结束后写的第一篇博客,关于中考他死了。 接下来还有FFT等一众博客要更新,只能慢慢来了。 部分算法为中考前集训学的,现在需要回忆下才能口胡出来,所以先更这篇昨天学习的容斥及广义容斥的姿势。 本文有部分参考于Parsnip的博文可以去他那里补充看看。 正文 容斥原理 这个大家或多或少都接触过,就是给出一些不同性质包含不同数量元素的集…
BZOJ4128 Matrix矩阵BSGS模板题
题面 给定矩阵A,B和模数p,求最小的x满足 A^x = B (mod p) 思路 一眼看去就是BSGS,很显然这个结论在矩阵中也同样适用,那么把乘法替换成矩阵乘法然后矩阵HASH判重即可。(就这么简单) 代码 #include<bits/stdc++.h> #define LL long long #define Mod 998244353…
BZOJ3994 [SDOI2015]约数个数和
题面 设$f(x)$为x的约数个数,给定$N$、$M$,求$\sum_{i=1}^{n} \sum_{j=1}^{m} f(i j)$ 思路 推导过程 有个定理$f(ij)=\sum_{x | i} \sum_{y | j}[g c d(x, y)=1]$。你问我如何推导,我只能告诉你无可奉告——这里纸太小,写不下。 然后大力推导以后数论分块即可,…