Re: [問題] 有一題我解不出來(哭)

看板CSCamp2009作者 (Mr.Banana)時間14年前 (2009/08/24 21:24), 編輯推噓4(406)
留言10則, 4人參與, 最新討論串6/6 (看更多)
想了一下 我決定這麼寫了 可是PO到zerojudge之後他說我逾時(泣) #include<iostream> using namespace std; int main(){ long long int a,i,j; while(cin>>a){ int sum=0; for(i=5;i<=a;i=i*5){ for(j=5;j<=a;j=j+5){ if(j%i==0) sum=sum+1; } } cout<<sum<<endl; } system("pause"); return 0; } 說我逾時了一秒~哭哭 不好意思喔|||||| 最近被計概荼毒 加上電腦被我重灌 所以從PTT上消失了頗久XD -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.129.196.144

08/24 22:12, , 1F
重複計算的地方太多了 試一組測資 2147483647~
08/24 22:12, 1F

08/24 22:13, , 2F
跑了1分鐘還沒出來= =
08/24 22:13, 2F

08/25 18:12, , 3F
可以稍微說一下是在做什麼的嗎?
08/25 18:12, 3F

08/26 01:51, , 4F
怎麼覺得一樓的數字很眼熟...
08/26 01:51, 4F

08/26 12:50, , 5F
該題測資的極限啊~ int的上限(2^31-1)~
08/26 12:50, 5F

08/26 12:51, , 6F
話說時間複雜度看起來大概是O(n/2 * logn) log底為5
08/26 12:51, 6F

08/26 12:52, , 7F
更正 O(n/5 * logn)
08/26 12:52, 7F

08/26 12:53, , 8F
nlogn的算法這題會TLE的Q Q
08/26 12:53, 8F

08/28 17:13, , 9F
好複雜喔(淚)
08/28 17:13, 9F

08/28 19:39, , 10F
總之就是算法太慢...測資可以到2147483647
08/28 19:39, 10F
文章代碼(AID): #1AafILcX (CSCamp2009)
討論串 (同標題文章)
文章代碼(AID): #1AafILcX (CSCamp2009)