（可能比较简洁，主要我自己看得懂，不懂得可以问我）
BSGS
求解ax≡ba^x \equiv bax≡b (mod(mod(mod p)p)p)的最小非负整数解xxx，(a,p)=1(a,p)=1(a,p)=1
显然xxx取值一定在[0,p−1][0,p-1][0,p−1]间。
考虑分块，拆成m=q+1m=\sqrt{q}+1m=q +1大小的块，使其覆盖全面，这样我们可以将xxx表示为i×m−ji \times m - ji×m−j，其中i∈[1,m]i \in [1,m]i∈[1,m]，j∈[0,m−1]j \in [0,m-1]j∈[0,m−1]。
再回推式子：
ai×m−j≡ba^{i\times m -j} \equiv bai×m−j≡b (mod(mod(mod p)p)p)
得到：
(am)i≡b×aj(a^m)^i \equiv b \times a^j(am)i≡b×aj (mod(mod(mod p)p)p)
我们可以用哈希表预处理出所有b×ajb\times a^jb×aj的值，遍历iii查询有无在模ppp意义下相同的值，输出即可。
模版题可以去luogu搜，我比较懒就不放传送门了。。
P2485 计算器
原题三合一，++经验。
但无解的情况要判清楚！
EXBSGS
比其原来就是不保证(a,p)=1(a,p)=1(a,p)=1。
我们令g=(a,p)g=(a,p)g=(a,p)，如果bbb modmodmod ggg ≠0\not=0=0 则无解，否则我们可以拆成：
ag×ax−1≡bg\frac{a}{g} \times a^{x-1} \equiv \frac{b}{g}ga ×ax−1≡gb (mod(mod(mod qg)\frac{q}{g})gq )
重复上面过程，知道无解或者(a,p)=1(a,p)=1(a,p)=1，显然操作次数在logp\log plogp 范围。
无论是BSGS还是EXBSGS，我认为判无解，0和1最要注意（也有可能是我太弱了吧，在这上面挂了挺多发的）。
P3306
神秘推柿子题，由题意得：
xi=ai−1×x1+b×∑i=0i−2ai(modx_i=a_{i-1} \times x_1 + b \times \sum_{i=0}^{i-2}a^i (modxi =ai−1 ×x1 +b×∑i=0i−2 ai(mod p)p)p)
最后自己手推一下就可以得到：
ai−1≡(t+b×(a−1)−1)×(b×(a−1)−1+x1)−1(moda^{i-1} \equiv (t + b \times (a-1)^{-1}) \times(b \times (a-1)^{-1}+x_1)^{-1} (modai−1≡(t+b×(a−1)−1)×(b×(a−1)−1+x1 )−1(mod p)p)p)
因为ppp为质数，一道BSGS的模板题。
但是，5min推柿子，花了60min调特判条件，绷不住了。。。
整除分块
一个神秘N\sqrt{N}N 级别技巧。
考虑一个基础问题：∑i=1n⌊ni⌋\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor∑i=1n ⌊in ⌋
打表发现取值为分为n\sqrt{n}n 块，令lll为左端点，则r=⌊n⌊nl⌋⌋r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloorr=⌊⌊ln ⌋n ⌋。
为什么rrr去这个数？我的理解是，当前我们处理的区间值为⌊ni⌋\lfloor \frac{n}{i} \rfloor⌊in ⌋，而这个值在nnn值域范围内最多有⌊n⌊nl⌋⌋\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor⌊⌊ln ⌋n ⌋这么多数。
再考虑，如果变成：∑i=1ni×⌊ni⌋\sum_{i=1}^{n} i \times \lfloor \frac{n}{i} \rfloor∑i=1n i×⌊in ⌋，怎么办？
显然，在一个区间内，⌊ni⌋\lfloor \frac{n}{i} \rfloor⌊in ⌋是不变的，变得是iii，用等差数列求和，或者前缀和都行。
P2261
根据余数性质nnn modmodmod i=n−i×⌊ni⌋i=n -i \times \lfloor \frac{n}{i} \rfloori=n−i×⌊in ⌋，提出常量，就是一个上面板子题目
P2260
比较爽的推柿子！
我们令n≤mn\le mn≤m，
根据容斥原理和取模性质，得到：
∑i=1n∑j=1m(n−i×⌊ni⌋)×(m−j×⌊mj⌋)−∑i=1n(n−i×⌊ni⌋)×(m−i×⌊mi⌋)\sum_{i=1}^{n} \sum_{j=1}^{m} {(n-i\times \lfloor \frac{n}{i} \rfloor)\times (m-j\times \lfloor \frac{m}{j} \rfloor)}-\sum_{i=1}^{n}{(n-i\times \lfloor \frac{n}{i} \rfloor)\times (m-i\times \lfloor \frac{m}{i} \rfloor)}∑i=1n ∑j=1m (n−i×⌊in
⌋)×(m−j×⌊jm ⌋)−∑i=1n (n−i×⌊in ⌋)×(m−i×⌊im ⌋)
再推：
(∑i=1nn−i×⌊ni⌋)×(∑j=1mm−j×⌊mj⌋)−n2m+∑i=1nn×i×⌊mi⌋+∑i=1nm×i×⌊ni⌋−∑i=1ni2×⌊ni⌋×⌊mi⌋(\sum_{i=1}^{n} {n-i\times \lfloor \frac{n}{i} \rfloor}) \times (\sum_{j=1}^{m}{m-j\times \lfloor \frac{m}{j} \rfloor})-n^2m+\sum_{i=1}^{n}n\times i \times \lfloor \frac{m}{i} \rfloor+\sum_{i=1}^{n}m \times i \times
\lfloor \frac{n}{i} \rfloor-\sum_{i=1}^{n} {i^2 \times \lfloor \frac{n}{i} \rfloor\times \lfloor \frac{m}{i} \rfloor}(∑i=1n n−i×⌊in ⌋)×(∑j=1m m−j×⌊jm ⌋)−n2m+∑i=1n n×i×⌊im ⌋+∑i=1n m×i×⌊in ⌋−∑i=1n i2×⌊in ⌋×⌊im ⌋
这里我们发现遇到了二维分块，相当于有两行多段区间相交起来，我们处理时只用对分别的区间右端点取一个min即可。
注：∑i=1ni2=16×n×(n+1)×(2×n+1)\sum_{i=1}^{n} {i ^ 2}=\frac{1}{6}\times n \times (n+1) \times (2\times n + 1)∑i=1n i2=61 ×n×(n+1)×(2×n+1)
所以我们就这样做完了：
P6583
非常神秘的整除分块！
首先有一个结论，就是若一个分数（最简形式）分母只含质因数222或555时才是有限小数。
那就考虑化简分数，令d=gcd(x,y)d=\gcd(x,y)d=gcd(x,y)且d∤2d\not|2d∣2且d∤5d\not|5d∣5，所以我们转化为a×db×d\frac{a\times d}{b\times d}b×da×d 。
考虑一个函数f(n)f(n)f(n)表示[1,n][1,n][1,n]有多少个数是形如2a×5b2^a\times 5^b2a×5b。
如何推？
先考虑2a×5b≤n2^a\times 5^b\le n2a×5b≤n ，
所以5b≤n2a5^b\le \frac{n}{2^a}5b≤2an ，
所以y∈[0,log5n2a]y\in [0,\log_5{\frac{n}{2^a}}]y∈[0,log5 2an ]。
枚举xxx使得2a≤n2^a\le n2a≤n，即可O(logn)O(\log n)O(logn)求出这个东西，那这个东西有啥用呢？
朴素的看，我们可以枚举ddd，aaa的取值范围为[1,⌊nd⌋][1,\lfloor \frac{n}{d} \rfloor][1,⌊dn ⌋]，bbb为其基础上只包含222，555质因数。
所以对于一个ddd，如果有cntbcnt_bcntb 个bbb满足条件，则贡献为cntb×⌊nd⌋cnt_b \times \lfloor \frac{n}{d} \rfloorcntb ×⌊dn ⌋。
所以Ans=∑d=1n[d∤2][d∤5]f(⌊nd⌋)×⌊nd⌋Ans=\sum_{d=1}^{n} {[d\not| 2] [d\not |5]f(\lfloor \frac{n}{d} \rfloor) \times \lfloor \frac{n}{d} \rfloor}Ans=∑d=1n [d∣2][d∣5]f(⌊dn ⌋)×⌊dn ⌋。
注意到这么一坨东西也可以整除分块，按照⌊nd⌋\lfloor \frac{n}{d} \rfloor⌊dn ⌋值分块即可。
考虑到前面两个限制，我们考虑一个容斥，在区间[1,x][1,x][1,x]内，满足d∤2d\not| 2d∣2且d∤5d\not |5d∣5的数有(x−⌊x2⌋−⌊n5⌋+⌊n10⌋)(x-\lfloor \frac{x}{2} \rfloor - \lfloor \frac{n}{5}\rfloor +\lfloor \frac{n}{10} \rfloor)(x−⌊2x ⌋−⌊5n ⌋+⌊10n ⌋)个。
这样就做完了。
原根
神秘知识点，定义可以去oi-wiki上了解，我感觉我没咋看懂，丢一个求原根的步骤吧
1. 判定 nnn 是否有原根：
根据数学定理，只有 n=2,4,pk,2pkn = 2, 4, p^k, 2p^kn=2,4,pk,2pk（其中 ppp 是奇素数，k≥1k \ge 1k≥1）这四种情况有原根。
2. 求 φ(n)\varphi(n)φ(n) 的质因数：
如果 ggg 是 nnn 的原根，则对于 φ(n)\varphi(n)φ(n) 的任意质因数 qqq，都有 gφ(n)q≢1(modn)g^{\frac{\varphi(n)}{q}} \not\equiv 1 \pmod ngqφ(n) ≡1(modn)。
3. 求最小原根 g0g_0g0 ：
从 1 开始枚举 ggg，利用上面的性质判定，找到第一个满足条件的 ggg。最小原根通常很小（O(n1/4)O(n^{1/4})O(n1/4) 级别），所以枚举很快。
4. 求出所有原根：
如果 g0g_0g0 是一个原根，那么所有的原根集合为 {g0k(modn)∣gcd(k,φ(n))=1,1≤k≤φ(n)}\{g_0^k \pmod n \mid \gcd(k, \varphi(n)) = 1, 1 \le k \le \varphi(n) \}{g0k (modn)∣gcd(k,φ(n))=1,1≤k≤φ(n)}。
持续更新中（字符串有点不想更了咋办）......
