数论的一些小小的性质总结
总结 一些 性质 数论
2023-09-11 14:14:52 时间
数论题,一定,要在草稿纸上写一遍!!这样思路会清晰很多!!
有公式或者特殊性质的条件的,一定要写在纸上推一推!!!
gcd的一些套路:
1.设一些未知数,设gcd为k,换个角度去看问题,比如先去枚举(质)因子,再去枚举倍数
2.一堆数的gcd为1,等价于它们所有数的因子重合小于n;两个数的gcd=1,它们的因子之间没有重合
3.相邻两数之间gcd=1(适用于构造题结论)
4.gcd(kx,kx+x)=x(差分可以证,提出因子也可以证)
5.gcd(ka, kb) = k·gcd(a, b)
6.gcd(a, b) = d,则gcd(a/d, b/d) = 1
7.考虑唯一分解定理,然后去考虑贡献
如果有涉及到最小质因子,就去考虑线性筛
如果有幂次,就去考虑这是不是小数据范围
、
8.因子的全局哈希,然后去枚举倍数
lcm的一些套路:
lcm(因子,倍数)=倍数
相关文章
- 本系列文章总结归纳了一些软件测试工程师常见的面试题,主要来源于个人面试遇到的、网络搜集(完善)、工作日常讨论等,分为以下十个部分,供大家参考。如有错误的地方,欢迎指正。有更多的面试题或面试中遇到的坑,
- 织物缝纫的一些知识总结
- 关于开发简易搜索引擎的一些总结和思考
- 读者学习《MATLAB入门100例》过程中的一些问题总结——不定期更新
- APP UI自动化测试思路总结全在这了
- 总结C#学习中的一些基础知识
- C# 对象和类型总结(二)
- PHP 开发 APP 接口 学习笔记与总结 - APP 接口实例 [7] APP 错误日志接口
- 对机器学习与数据竞赛的一些总结(转)
- 《响应式Web图形设计》一7.5 总结
- Swift之手势总结
- 关于CPU的一些基本知识总结
- 【PyTorch教程】03-张量运算详细总结
- 学习总结9/16
- 华为入侵检测思绪总结
- 总结—二分答案求解问题
- JVM调优总结:一些概念
- 【Verilog基础】关于Clock信号的一些概念总结(clock setup/hold、clock tree、clock skew、clock latency、clock transition..)
- 匆忙--一个大龄十年老程序员战战兢兢的应对中年危机的2019年总结与2020年展望
- PAT归纳总结——关于图的一些总结
- PAT归纳总结——关于二叉树的一些总结