从入门到"啊哈"的那些事儿
说实话，刚接触数论那会儿，我整个人是懵的，什么质数、同余、欧拉函数……一堆名词砸过来，脑袋嗡嗡的，但后来慢慢啃下来才发现，哎哟，这东西其实挺有意思的，而且做题的时候真的香！今天就跟大家唠唠数论基础用法详解这个话题,把我踩过的坑和悟出来的门道都掏心窝子分享给你。
质数：数论的"地基"，别小看它
质数这玩意儿，定义简单得不能再简单——只能被1和它本身整除的大于1的整数，但你别说，越简单的东西越有门道。数论基础用法详解里头,质数判定和筛法是绕不开的第一关。
朴素判定法？试除到√n就行，简单粗暴，但你要是遇到1e7级别的数据，一个个判不得累死？这时候埃氏筛就登场了——把每个质数的倍数都标记掉，剩下的就是质数，时间复杂度O(n log log n)，香得很！再往上还有线性筛（欧拉筛），每个合数只被它的最小质因子筛一次，O(n)的复杂度，简直是强迫症的福音，我当时写线性筛的时候，那个 if(i % prime[j] == 0) break; 琢磨了半天才明白为啥要break，你要是也卡在这儿，别急，画个表手动跑一遍就通了,真的！
同余与快速幂：竞赛里的"常客"
同余这个概念，说白了就是"余数相同"，a ≡ b (mod m) 表示a和b除以m余数一样，听起来平平无奇对吧？但数论基础用法详解里,同余的威力可大了去了。
最典型的就是快速幂，你想啊，2的100次方，直接算？long long都得爆，但用快速幂配合取模，边乘边模，O(log n)就搞定了，我记得第一次手写快速幂的时候，那个二进制拆分的思想让我拍大腿——原来指数还能这么玩！代码也就十来行，但那种"啊哈"的感觉,至今难忘。
还有逆元，除法在模意义下不能直接除啊，得乘逆元，费马小定理（p为质数时，a^(p-1) ≡ 1 mod p）给了一个漂亮的解法：a的逆元就是a^(p-2) mod p，配上快速幂，齐活！扩展欧几里得也能求逆元，而且不要求模数是质数，适用范围更广，这俩方法我都建议你掌握，考试的时候看情况挑着用,稳！
GCD与LCM：老朋友了，但你真的会用吗？
辗转相除法求最大公约数，这个大家中学就学过吧？gcd(a, b) = gcd(b, a % b)，一行递归搞定，优雅得不行，但数论基础用法详解要提醒你：别只会求个gcd就完事儿了！
扩展欧几里得才是重头戏——它不光求gcd，还能顺带求出 ax + by = gcd(a, b) 的一组解，这个在解同余方程、求逆元的时候简直是神器，我当初学的时候，递归回溯那部分绕得我头晕，后来拿纸笔一步步推，才把 x 和 y 的更新关系理顺：x = y1, y = x1 - (a/b) * y1，你要是也在这儿卡壳，别慌，多推几遍,肌肉记忆就有了。
还有LCM，lcm(a, b) = a / gcd(a, b) * b，注意先除后乘防溢出！这个小细节，我当年WA了好几次才长记性,血泪教训啊。
组合数与卢卡斯定理：大数取模的救星
组合数C(n, m)在模质数p下怎么算？n小的时候递推或者阶乘加逆元都行，但n大到1e18呢？阶乘根本存不下啊！这时候卢卡斯定理就派上用场了：C(n, m) mod p = C(n%p, m%p) * C(n/p, m/p) mod p，递归下去，把大问题拆成小问题，第一次看懂这个定理的证明时，我是真的服气，数学家的脑子咋长的……
写在最后：多动手，别光看
唠了这么多，其实数论基础用法详解最核心的一条心得就是：别光看，动手写！ 数论这东西，看懂了和写出来是两码事，写出来和调通了又是两码事，质数筛、快速幂、扩展欧几里得、卢卡斯定理，这几个模板你挨个手敲几遍，再找几道板子题练练,慢慢就有感觉了。
前期可能会觉得枯燥，但熬过那阵子，你会发现数论题其实特别"讲道理"——思路对了，代码短得惊人，加油吧，有什么卡住的地方，欢迎回来一起讨论,咱们互相种草哈哈！