首页 > 代码库 > POJ 1142 Smith Numbers（分治法+质因数分解）
POJ 1142 Smith Numbers（分治法+质因数分解）
http://poj.org/problem?id=1142
题意：
给出一个数n，求大于n的最小数，它满足各位数相加等于该数分解质因数的各位相加。
思路：
直接暴力。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <queue> 6 #include <cmath> 7 using namespace std; 8 9 int n;10 11 int cacl(int x)12 {13 int sum = 0;14 while (x)15 {16 sum += x % 10;17 x /= 10;18 }19 return sum;20 }21 22 bool isprime(int x)23 {24 int m = sqrt(x + 0.5);25 for (int i = 2; i <= m; i++)26 {27 if (x%i == 0) return false;28 }29 return true;30 }31 32 int solve(int x)33 {34 if (isprime(x))35 return cacl(x);36 else37 {38 int m = sqrt(x + 0.5);39 for (int i = m; i >1;i--)40 if (x%i == 0)41 return solve(i) + solve(x / i);42 }43 }44 45 int main()46 {47 //freopen("D:\\input.txt", "r", stdin);48 while (~scanf("%d", &n) && n)49 {50 for (int i = n + 1;; i++)51 {52 if (!isprime(i) && cacl(i) == solve(i))53 {54 printf("%d\n", i);55 break;56 }57 }58 }59 return 0;60 }
POJ 1142 Smith Numbers（分治法+质因数分解）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。