糯米
TI DaVinci, gstreamer, ffmpeg
隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
數據加載中……
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
糯米
閱讀(875)
評論(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
管理
Powered by:
C++博客
Copyright © 糯米
導航
管理
隨筆分類
Algorithm(9)
(rss)
Linux(6)
(rss)
Lisp(4)
(rss)
Misc(13)
(rss)
Perl(3)
(rss)
POJ(126)
(rss)
Python(1)
(rss)
Links
ELinux
Unix Stackexchange
最新評論
1.?re: POJ 2374 Fence Obstacle Course 線段樹+動態規劃
@CWQBUPT
因為你缺少了二分的過程,線段樹查找O(logn),而你的查找O(n)
--hez2010
2.?re: lisp let,let*
寫的很詳細,有點理解了。原來 let* 會把上一個表達式的計算結果帶到下一個計算結果上面去:)
--creamidea
3.?re: [轉]Stairway to Heaven 歌詞分析
評論內容較長,點擊標題查看
--劉修墨
4.?re: POJ 2132 Cow Math 二分[未登錄]
評論內容較長,點擊標題查看
--糯米
5.?re: POJ 1945 Power Hungry Cows 終極打表[未登錄]
評論內容較長,點擊標題查看
--糯米
閱讀排行榜
1.?[轉]休息五分鐘,學幾個bash快捷鍵(17643)
2.?[轉] Floyd 算法原理(5083)
3.?POJ 2018 Best Cow Fences 牛題(3259)
4.?POJ 3150 Cellular Automaton 矩陣乘法+二分(3186)
5.?POJ 1945 Power Hungry Cows 終極打表(2812)
久久久久99精品成人片欧美
|
久久久精品免费国产四虎
|
久久超乳爆乳中文字幕
|
久久婷婷五月综合色高清
|
无码任你躁久久久久久久
|
777米奇久久最新地址
|
狠狠色丁香久久婷婷综合蜜芽五月
|
久久久久人妻一区精品色
|
精品99久久aaa一级毛片
|
国产精品久久久久久五月尺
|
久久久久亚洲AV无码专区首JN
|
亚洲狠狠久久综合一区77777
|
久久久久亚洲AV片无码下载蜜桃
|
久久精品嫩草影院
|
成人资源影音先锋久久资源网
|
狠狠人妻久久久久久综合蜜桃
|
亚洲精品tv久久久久久久久
|
久久精品国产2020
|
久久久久亚洲av毛片大
|
日本久久中文字幕
|
久久99热狠狠色精品一区
|
久久久久久国产a免费观看黄色大片
|
久久精品国产精品亚洲
|
26uuu久久五月天
|
久久综合香蕉国产蜜臀AV
|
7777精品伊人久久久大香线蕉
|
国产精品久久久亚洲
|
欧美熟妇另类久久久久久不卡
|
欧美与黑人午夜性猛交久久久
|
国产精品一久久香蕉国产线看
|
久久妇女高潮几次MBA
|
久久婷婷人人澡人人
|
国产福利电影一区二区三区久久久久成人精品综合
|
精品久久久久久久久中文字幕
|
久久综合久久综合亚洲
|
久久久久黑人强伦姧人妻
|
婷婷综合久久中文字幕
|
久久久久久免费一区二区三区
|
99999久久久久久亚洲
|
久久精品国产99国产精偷
|
AAA级久久久精品无码片
|