TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

90.5% (19/21)

Submission's AC Ratio

54.1% (33/61)

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

4

Sample Output

4

Hints

$N=4$時(1,2)(1,3)(1,4)(2,4)都符合條件。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第四次模擬賽pB

Subtasks

For Testdata: 0 ~ 4, Score: 8
For Testdata: 5 ~ 9, Score: 22
For Testdata: 10 ~ 14, Score: 70
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144