1556 . Weep
TopCoder
Tags
Description
在遙遠的國度，有一種狼羊混種的神秘物種：Wolf-Sheep，簡稱Weep.
Weep除了會哭(?)之外，還會進行自相殘殺的行為。這也非常合理，畢竟他們有一半是狼，一半是羊。
Peew, 一個遙遠國度的牧Weep人，豢養著$N$隻Weep，由$1$編號到$N$。平時他和別人聯絡都是透過他的Weep進行：他會派兩隻Weep一同前往目的的並且將物品交給目標。
如同陳舊的劇情設定，只要有兩隻Weep單獨相處，就可能有其中一隻會被另一隻吃掉。然而Weep並不會隨意地亂吃別Weep：一隻編號A的Weep會吃掉一隻編號B的Weep若且唯若B>A而且A整除B。
雖然Peew也知道Weep有如此陋習，但管理著$N$隻Weep並不是簡單的事，他實在無瑕確認派譴的兩隻Weep是否會吃掉他的同伴，所以他希望能計算出滿足第一隻Weep會吃掉第二隻Weep的Weep對個數以做為參考。
Input Format
每組測資僅包含一行，內含一個正整數$1\leq N\leq 10^ {14}$，代表Weep的個數。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $N\leq 10^ 4$ | 8 |
| 2 (5~9) | $N\leq 10^ 8$ | 22 |
| 3 (10~14) | 無限制 | 70 |
Output Format
輸出一個整數，代表符合題意的Weep對個數。
Sample Input 1
4
Sample Output 1
4
Hints
$N=4$時(1,2)(1,3)(1,4)(2,4)都符合條件。
Problem Source
Problem set / Description by Paupière
建國中學105學年度校內第四次模擬賽pB
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 8 |
| 2 | 5~9 | 22 |
| 3 | 10~14 | 70 |