天天看點

2015 Multi-University Training Contest 1 - 10010 Y sequence Y sequence Problem's Link:  http://acm.hdu.edu.cn/showproblem.php?pid=5297

Mean: 

 有連續數列A={1,2,3,4,5,6,7,8 .....},将可以表示成a^b次方的數删除,a={1,2,3,4,5...},而2<=b<=r,删除後形成一個新的數列,求這個數列的第n項。

analyse:

很有趣的一道數論題。

對于給定的一個n,如果我們知道1~n中被删除的數字為k個,那麼答案一定大于等于n+k,是以向後至少移動k個數。

但是n~n+k這一段中也可能含有被删除的數字,是以我們再求n~n+k這一段中被删除的數字的個數,假設為x1個,那麼我們就得到了一個比x更精确的數字x1,即:我們要得到第n項,至少需要從n向後移動x1位。

但是移動x1位後同樣還可能存在以上的問題,那麼什麼時候停止呢?答案是:當本次算的xi和上次算的xi相等時,就說明這個值是固定的了,也就是最終的精确值,代表第n項就是n+xi,也就是最終的答案。

有了這個理論基礎後,我們來考慮如何求得1~n中有多少個數字能夠表示成次幂形式。

解決這個問題的方法是反函數。幂的反函數是依然是幂函數,指數取導就行。

例:10以内能表示成a^2的數的個數為:pow(10,1/2) ; 100以内能表示成a^4的數的個數是:pow(100,1/4).

還有一個問題:在删除數的時候,a^6的數已經被a^2和a^3的數删過了,這樣就造成了重複删除。

這兒就需要容斥原理來解決:隻需要删質數次幂的數就行,而且還需要把質數的乘積(多删的)删除的數字加回來。

詳情參考大牛部落格:http://blog.csdn.net/firstlucker/article/details/46991885

Time complexity: O(N)

Source code: 

  

繼續閱讀