POJ 1142 Smith Numbers 數字游戲
題目大意:
有個叫smith的人,閑得蛋疼,做了如下定義:
如果一個數分解的質因數的所有位數的和加在一起等于該數字的所有位數的和,則這個數是“smith數”。
比如:
另外:素數不是“smith數”
給出一個數字,求出比該數字大的數中最小的“smith數”。
思路:
按照常規方法,從2一直向上掃描,遇到能除的就除,求出數字的質因數。
但要注意,如果掃到大于該數字的平方,就沒必要繼續掃了,一定是素數。沒加這個就是TLE。
另外,如果現有的和已經超過了最大的可能和,也沒必要繼續掃了。
#include <stdio.h>
#include <math.h>

__inline int digit_sum(int val)


{
int i;

for (i = 0; val; val /= 10)
i += val % 10;
return i;
}

__inline int is_smith(int val)


{
int i, fs, max_sum, left, sum, sq;

max_sum = digit_sum(val);
sum = 0;
left = val;
sq = (int)sqrt((float)left);

for (i = 2; i <= sq; i++)
{
if (left % i)
continue;
fs = digit_sum(i);

while (!(left % i))
{
sum += fs;
left /= i;
}
if (left == 1)
return sum == max_sum;
if (sum > max_sum)
return 0;
sq = (int)sqrt((float)left);
}

return sum && digit_sum(left) + sum == max_sum;
}

int main()


{
int j, i, val;


while (1)
{
scanf("%d", &val);
if (!val)
break;
for (val++; !is_smith(val); val++);
printf("%d\n", val);
}

return 0;
}
有個叫smith的人,閑得蛋疼,做了如下定義:
如果一個數分解的質因數的所有位數的和加在一起等于該數字的所有位數的和,則這個數是“smith數”。
比如:
4937775= 3*5*5*65837
4+9+3+7+7+7+5= 42
3+5+5+6+5+8+3+7=42
則4937775是“smith數”。4+9+3+7+7+7+5= 42
3+5+5+6+5+8+3+7=42
另外:素數不是“smith數”
給出一個數字,求出比該數字大的數中最小的“smith數”。
思路:
按照常規方法,從2一直向上掃描,遇到能除的就除,求出數字的質因數。
但要注意,如果掃到大于該數字的平方,就沒必要繼續掃了,一定是素數。沒加這個就是TLE。
另外,如果現有的和已經超過了最大的可能和,也沒必要繼續掃了。

































































posted on 2010-02-27 15:29 糯米 閱讀(871) 評論(0) 編輯 收藏 引用 所屬分類: POJ