首页 > 代码库 > 数学的强大~~ HDU 2092
数学的强大~~ HDU 2092
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2092
这道题虽然简单，但是很受启发。
题目给出两个整数A, B,，问是否存在两个整数，使得和为A，乘积为B。
解题过程：
首先想到的办法，当然是用一个二重循环枚举。
#include <cstdio>#include <cstdlib>int main(){ int a, b; while(~scanf("%d%d", &a, &b)){ if(a == 0 && b == 0) break; int n; if(a < 0 || b < 0) n = abs(a) > abs(b) ? a : b; else n = a > b ? b : a; if(n < 0) n = -n; int flag = 0; for(int i = -n; i <= n; i++) for(int j = -n; j <= n; j++) if(i+j == a){ if(i*j == b){ flag = 1; break; } } if(flag == 1) printf("Yes\n"); else printf("No\n"); } return 0;}
结果：超时~~ 显然这个方法是O(n^2)的时间复杂度，无论怎样优化边界也是徒劳
其实完全不必推公式，仅仅就解一个方程即可：a+b = n; a*b = m;
则可以用a来表示b， 从而把时间复杂度降为O(n)~~~ 即 b = n - a //这里用第二个公式显然会造成溢出
#include <cstdio>#include <cstdlib>int main(){ int a, b; while(~scanf("%d%d", &a, &b)){ int n; if(a == 0 && b == 0) break; if(a < 0 || b < 0) n = abs(a) > abs(b) ? a : b; else n = a > b ? b : a; if(n < 0) n = -n; int flag = 0; for(int i = -n; i < n; i++) if(i*(a-i) == b){ flag = 1; break; } if(flag == 1) printf("Yes\n"); else printf("No\n"); } return 0;}
可见，数学的强大~~~
数学的强大~~ HDU 2092
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。