在遙遠的國度,有一種狼羊混種的神秘物種: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對個數以做為參考。
每組測資僅包含一行,內含一個正整數$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 |
輸出一個整數,代表符合題意的Weep對個數。
$N=4$時(1,2)(1,3)(1,4)(2,4)都符合條件。
Problem set / Description by Paupière
建國中學105學年度校內第四次模擬賽pB
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 8 |
2 | 5~9 | 22 |
3 | 10~14 | 70 |