Re: [ACM ] 10290 {Sum+=i++} to Reach N

看板C_and_CPP (C/C++)作者bleed1979 (十三)時間16年前 (2009/05/03 20:38)推噓6(6推 0噓 5→)

留言11則, 5人參與討論串1/1

※ 引述《DJWS (...)》之銘言： : 這一題會用到質因數分解 : 我本想使用 Pollard's rho algorithm : 不過N的範圍實在太大了 (9*10^14) : 運算過程當中無法把數值直接放進一個64bit的整數裡 : 這條路不知可不可行... : 想請教各位是什麼方式通過這題的？唉　這題我的程式只能剛好通過ACM UVa上的測資只能說測資不夠刁鑽　如果我將程式修正的話　就會TLE 先講解這題在問什麼這題要求某個數　他的奇因數有幾個以30來說 1, 2, 3, 5, 6, 10, 15, 30 所以答案是　4 ( 1, 3, 5, 15 ) 比較快的方法就是求奇質因數指數 + 1後相乘 30 = 2^1 * 3^1 * 5^1 所以答案為 (1 + 1) * (1 + 1) = 4 如果有某個數的質因數分解是 2^3 * 3^2 * 7^1 答案為 ( 2 + 1 ) * ( 1 + 1 ) = 6 質因數2可以完全不管他所以我們得到題目輸入的n時先把所有的2除盡 for( ; n > 1 && n % 2 == 0; n /= 2 ); 之後的n開始質因數分解並對奇質因數的指數下功夫如果還在 for(k = 3; k <= n; k += 2) 一定是TLE　我們的k一次跳一定是跳質數所以又回到求質數的老問題不管用任何方法總之要先求出一群質數並放入陣列 range到9E14　所以理論上要求到3E7的質數才準而我賭測資不會超過10E6的質數所以我把range下修到10E6 如此才AC的　AC秒數是2.150　也差點TLE了如果我要修正程式到3E7的話　還是TLE 大致上是這樣至於質因式分解這個大家都很熟才對附帶一提 PKU OJ 2140 和這一題一模一樣但他的測資只到10E7　可以輕鬆巴假的短碼達人這本書有提到不過該書裡面的code對這題來說只是code短而已　速度上還是很慢的 Pollard's rho algorithm 這個演算法的缺點在於如果數是composite的話也就是這個數是好幾個質數的乘積就要花很多時間去換 c 來run這個演算法我用大數實作這個演算法上傳　還是TLE Bleed -- World of bleed1979 http://bleed1979.myweb.hinet.net/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.168.133.230