久久久久久久久久码影片,免费不卡欧美自拍视频,久久久久久久久久久久久久一区

POJ 1142 Smith Numbers 數字游戲

題目大意：
有個叫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數”。
另外：素數不是“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;

}

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

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: POJ 3123 Ticket to Ride 高效解法 POJ 3123 Ticket to Ride 動態規劃+Minimal Steiner Tree Minimal Steiner Tree 簡介 POJ 3122 Pie 二分 POJ 3121 The SetStack Computer 哈希 POJ 3120 Sudoku 搜索 POJ 3156 Interconnect 圖論+數論 POJ 3155 Hard Life 最大密度子圖 POJ 3154 Graveyard 模擬 POJ 3150 Cellular Automaton 矩陣乘法+二分

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

糯米

POJ 1142 Smith Numbers 數字游戲

導航

隨筆分類

Links

最新評論

閱讀排行榜