5156
整理日期按学习顺序编排，不代表原始发表时间。实际整理于 2026-10-23。
难度为阅读建议，可从 ACM 学习索引 按阶段阅读。
https://www.acwing.com/problem/content/5156/
对于能够被某个数整除的数的特征的一些总结
- 当我们要枚举一个数的后三位来判断这个数是不是能被8整除，可能会遇到这个数不足三位的情况，可以积累一个技巧，在数前面加两个前导零，这样枚举各位百位十位的时候，就可以枚举到个位数和两位数的情况。
下面两种写法等价，第一种是第二种代数变形后的结果。
1 | int x = s[i] * 100 + s[j] * 10 + s[k] - 111 * '0'; |
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！
相关推荐
整理日期：2026-09-09
容斥原理应用Acwing890借鉴题解
参考文献 简单的容斥原理介绍请看下图： C++ 代码 简单的容斥原理介绍请看下图： 本题思路： 将题目所给出的m个数可以看成是m位的二进制数，例如 当p[N]={2,3}时，此时会有01,10,11三种情况 而二进制的第零位表示的是p[0]上面的数字2,第1位表示p[1]上面的数字3 所以当i=1时表示只选择2的情况，当i=2（10）时,表示只选择3的情况,当i=3时,表示2和3相乘的情况 在过程中可以用标记变量t记录,可以按照t的值来选择是”+”还是“-” 代码如下： 12345678910111213141516171819202122232425262728293031323334353637383940#include#includeusing namespace std;typedef long long LL;const int N=20;int p[N];int main(){ int n,m; cin>>n>>m; for(int i=0;i>p[i]; int res=0; ...
整理日期：2026-09-10
矩阵乘法
123456789101112131415161718192021222324252627282930313233343536373839int n, m;int k;struct matrix{ int c[101][101]; matrix(){memset(c,0,sizeof c);} };matrix operator*(matrix &a,matrix &b){ matrix t; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ for(int g=1;g<=m;g++){ t.c[i][j]+=a.c[i][g]*b.c[g][j]; } } } return t;}void solve(){ cin>>n>>m>>k; matrix a,b; for(int...
整理日期：2026-09-08
质因数分解
acwing的最基础模板 https://www.acwing.com/blog/content/406/ 知乎大佬给的各种数据范围模板大全：https://zhuanlan.zhihu.com/p/591377294 对于其中的一部分进行提炼形成自己的模板 1.使用场景：假设有n个数需要分解，每个数最大可能是N,下面给出的这种代码的时间复杂度是O(nlogN)O(nlogN)O(nlogN) 思想：通过O(n)O(n)O(n)线性筛预处理过程中记录范围内每个数的最小质因数，分解时每个数的最多被计算O(logN)O(logN)O(logN)次。 1234567891011121314151617181920//预处理：for (int i = 2; i < N; i++)minp[i] = i;//通过这个初始化省下bool数组空间int cnt = 0;for (int i = 2; i < N; i++) { if (minp[i] == i) prime[cnt++] = i; for (int j = 0; j < cnt...
整理日期：2026-07-15
20230723牛客round4D题：给出一个大数的所有约数，通过dfs用质因子反向构造约数
两个正整数a，b，请问a∗b有哪些因子 1≤a,b≤1e9 求因子的数量并给出所有因子 本题无脑的暴力显然不能过，但用set存数，加上考虑到a*b的所有约数其实就是a的所有约数和b的所有约数分别相乘(核心） 补充常识：int范围内数的约数个数最多为1600，2e9数的约数个数最多为1536，这也是本题能这样暴力的基础 https://blog.csdn.net/qq_40438165/article/details/122030763 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <bits/stdc++.h>using namespace std;# define int long longconst int N = 1e5 + 10;const int M = 2e5 + 10;const int inf = 0x3f3f3f3f;const int mod = 998244353;int n,...
整理日期：2026-05-03
Kummer定理
Kummer定理 设 vp(n)v_p(n)vp(n)表示 n 的质因数分解中质数 p 的幂次，则： vp(n!)=∑i=1∞[npi]v_p(n!)=\sum\limits_{i=1}^\infty\left[\dfrac{n}{p^i}\right]vp(n!)=i=1∑∞[pin] 推论： vp(Cn+mm)=vp((n+m)!)−vp(m!)−vp(n!)=∑i=1∞[n+mpi]−∑i=1∞[mpi]−∑i=1∞[npi]=∑i=1∞([n+mpi]−[mpi]−[npi])\begin{aligned} v_p(\text{C}_{n+m}^m)&=v_p((n+m)!)-v_p(m!)-v_p(n!) \\ &=\sum\limits_{i=1}^\infty\left[\dfrac{n+m}{p^i}\right]-\sum\limits_{i=1}^\infty\left[\dfrac{m}{p^i}\right]-\sum\limits_{i=1}^\infty\left[\dfrac{n}{p^i}\right]...
整理日期：2026-05-04
gausstmp
当我们枚举到第 iii 个变量，且前 iii 个变量都不是自由元时，如果第 i∼ni\sim ni∼n 行中这个变量的系数均为 000，那么第 iii 个变量是自由元。 [a1,1a1,2a1,3a1,4a1,50a2,2a2,3a2,4a2,5000a3,4a3,5000a4,4a4,50000a5,5|c1c2c3c4c5]\left[\begin{matrix} a_{1,1} & a_{1,2} & a_{1, 3} & a_{1,4} & a_{1,5} \\ 0 & a_{2,2} & a_{2, 3} & a_{2,4} & a_{2,5} \\ 0 & 0 & \color{red}{0}& a_{3,4} & a_{3,5} \\ 0 & 0 & 0 & a_{4,4} & a_{4,5} \\ 0 & 0 & 0 & 0 & a_{5,5} \end{matrix} \middle...
最新文章