首页 > 代码库 > UVa 11621 - Small Factors
UVa 11621 - Small Factors
题目:找到不小于给定数n的,仅以2,3为因数组成的数字。
分析:数论,贪心,分治。
利用两根指针,分别代表乘2,与乘3的队列,队列为至今生成的数字,初始为{1};
然后,每取两个指针对应元素*2和*3的值中最小的即为未找到的数字中最小的;
注意,可能生成重复数据,不要存进去(重复数据,一定连续产生)。
说明:打表计算,二分查询输出即可。
#include <iostream> #include <cstdlib> #include <cstdio> using namespace std; int next[330]; int bs(int key, int r) { int l = 0,m; while (l < r) { m = (l+r)/2; if (next[m] < key) l = m+1; else r = m; } return r; } int main() { int two = 0,three = 0,count = 0; next[0] = 1; while (next[count] > next[count-1]) { if (next[two]*2 < next[three]*3) next[++ count] = next[two ++]*2; else { if (next[three]*3 == next[two]*2) two ++; next[++ count] = next[three ++]*3; } } int n; while (cin >> n && n) cout << next[bs(n, count)] << endl; return 0; }
UVa 11621 - Small Factors
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。