题面：
求n次整系数方程\(\sum_{i=1}^{n} a_ix^i = 0\)在区间\([1,m]\)上的整数解

解法：

1.暴力

O(NM) 暴力枚举+解方程

2.假设只要求一个解

瞎搞做法

引入参数T,选取T的整数倍作为标志点，在两个标志点间用勘根

时间复杂度O(\frac{T}{M} \time T) ， 取\(T = \sqrt{M}\)时最优

3.假设\(a_i\)很小

由整数方程解的性质，设该解为\(\frac{p}{q}\)，可得

• \(q|a_1\)
• \(p|a_n\)
• \(q|p\)

做法1: 枚举\(a_i\)的所有因子

做法2: 只用枚举a_1,a_n共有的所有质因子，降为\(O(log a_1)\)

那么总时间复杂度\(O(nloga_1+n)=O(nloga_1)\)

最新文章

1. socket编程与利用进程进行多并行连接
2. new NABCD
3. ASP.NET Cookie 概述【转】
4. play framework (一)
5. 导出excel的简单方法
6. ToArray()和IEnumerable<T>，List<T>
7. express4.x的使用
8. 【NOI2014】起床困难综合症（贪心）
9. DH密钥交换非对称加密
10. vs2015配置OpenCV遇到的问题
11. Virtualization
12. Android实现图片的压缩、旋转工具类
13. 用OZ工具制作openstack镜像
14. Django实现注册页面_头像上传
15. Oracle partition by 使用说明
16. C#批量插入数据到Sqlserver中的四种方式 - 转
17. Leetcode 461.汉明距离 By Python
18. 浅谈分词算法（3）基于字的分词方法（HMM）
19. CGAffineTransform 缩放 / 旋转 / 平移
20. 从客户端(ASPxFormLayout1$txtRule="<YYYY><MM><DD><XXXX>")中检测到有潜在危险的 Request.Form 值

热门文章

1. UVA - 548 Tree（二叉树的递归遍历）
2. 分享一个php加密字符串类。
3. 学术Essay写作如何体现逻辑的应用
4. java嵌套循环练习
5. 将已有微信小程序转换为多端应用
6. k8s资源pod yaml文件分析
7. jQuery元素的左右移动
8. 关于torch.nn.Conv2d的笔记
9. 2，The AudioContext was not allowed to start.
10. 程序员：java中直接或间接创建线程的方法总结