TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

95.5% (42/44)

Submission's AC Ratio

60.9% (84/138)

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3