|
Description |
题目描述 |
|
While skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University, noticed that the telephone number of his brother-in-law H. Smith had the following peculiar property: The sum of the digits of that number was equal to the sum of the digits of the prime factors of that number. Got it? Smith's telephone number was 493-7775. This number can be written as the product of its prime factors in the following way: 4937775= 3*5*5*65837 The sum of all digits of the telephone number is 4+9+3+7+7+7+5= 42,and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+3+7=42. Wilansky was so amazed by his discovery that he named this kind of numbers after his brother-in-law: Smith numbers. As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number, so he excluded them from the definition. Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036.However, Wilansky was not able to find a Smith number that was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers that are larger than 4937775! |
阿尔伯特·威兰斯基是一位理海大学的数学家，在1982年浏览他自己的电话薄时，注意到他的表兄弟（Harold Smith）H. Smith的电话号码有有如下特点：各位上的数字相加等于分解质因数后各位上的数字相加。懂否？史密斯的电话号码是493-7775。这个数字可被分解质因数致如下形式： 4937775= 3*5*5*65837 这个电话号码各位数字的和是4+9+3+7+7+7+5= 42，并且与分解质因数后各位数字的和相等3+5+5+6+5+8+3+7=42。威兰斯基感觉很神奇就以他的表兄弟命名：史密斯数。 不过这个性质对每个质数都成立，因此威兰斯基后来把质数（分解不能）从史密斯数的定义中剔除了。 威兰斯基在the Two Year College Mathematics Journal发表了关于史密斯数的论文并且列出了一整套史密斯数：举个栗子，9985是史密斯数，6036也是。但是威兰斯基没能找到比他表兄弟电话号码4937775更大的史密斯数，你可以当条红领巾！ |
|
Input |
输入 |
|
The input file consists of a sequence of positive integers, one integer per line. Each integer will have at most 8 digits. The input is terminated by a line containing the number 0. |
输入文件由一列正整数组成，每行一个整数。每个整数最多8位。数字0表示输入结束。 |
|
Output |
输出 |
|
For every number n > 0 in the input, you are to compute the smallest Smith number which is larger than n, and print it on a line by itself. You can assume that such a number exists. |
对于每个n>0的输入，你要算出大于n的最小史密斯数，输出一行。你可以认为结果是存在的。 |
|
Sample Input - 输入样例 |
Sample Output - 输出样例 |
|
4937774 0 |
4937775 |
【题解】
首先，这道题是水题，不然就会和某个人一样觉得要用Pollard's rho算法……
注意几点就可以了：
①可以暴力。②素数不是史密斯数。③从n+1开始找。
④题目描述和输入输出分开看，并不是要你找4937775后的史密斯数。
【代码 C++】
#include<cstdio>
#include<cstring>
#include<cmath>
int prime[];
void rdy(){
bool temp[];
memset(temp, , sizeof(temp));
prime[] = ;
int i = , j, pi = ;
for (i = ; i < ; i += ){
if (temp[i]) continue;
else{
for (j = i << ; j < ; j += i) temp[j] = ;
prime[++pi] = i;
}
}
prime[] = ;
}
int digitSum(int now){
int sum = ;
while (now) sum += now % , now /= ;
return sum;
}
int find(int now){
int i = , ed = sqrtf(now) + 0.5;
if (ed > ) ed = ;
for (; prime[i] <= ed; ++i){
if (now%prime[i] == ) return prime[i];
}
return ;
}
int change(int now){
int sum = , temp, stp = ;
while (now > ){
temp = find(now);
if (temp) sum += digitSum(temp), now /= temp, ++stp;
else sum += digitSum(now), now = ;
}
if (stp) return sum;
return ;
}
int main(){
rdy();
int n;
while (scanf("%d", &n)){
if (n++){
while (digitSum(n) != change(n)) ++n;
printf("%d\n", n);
}
else break;
}
return ;
}
POJ 1142