一道题目起码要思考二十分钟如果没有思路在去看题解,加油 hh
数论公式
1.逆元:除法不满足分配率,将a转化为a的逆元
(a ÷ b) % p = (a % p × W(b的逆元) % p) % p
2.求逆元:使用费马小定理、扩展欧几里得算法。费马小定理
:快速幂求逆元
3.费马定理a/b % p = a % (b * p) / b
4.1到n中p的倍数有多少个:n/p
5.n的阶乘中因子p的个数res :在n大于零的情况下不断进行res += n / p, n /= p;
题目整理
1.图论
1.dfs,树的遍历,叶子节点
2.$dp$
1.树状数组,DP,离散化,数据结构优化求前缀最大值,从而优化DP过程
3.数论
1.因子,最长连续因子分解
(pat连续因子)求一个数字的最长连续因子,第一维遍历起点,通过sum往后累加,判断是否能够被n整除。更新长度
2.进制问题,推公式
4.模拟问题
1.公约数,有理数连续求和