TopCoder

Thumb 100
johnchen902
我才不會讓你知道我有中二病的呢,哼!

User's AC Ratio

72.7% (8/11)

Submission's AC Ratio

38.1% (16/42)

Tags

Description

在令每隻魯蛇都感到傷心與絕望的聖誕假期,眼鏡行的墨鏡還是跟往常一樣熱銷;不一樣的是,你,在平安夜的時候鼓起勇氣向她告白,得到的回覆卻是:

「可是…我已經許了聖誕願望了…」
「? 什麼聖誕願望?」
「我和聖誕老人說如果他覺得我是個乖小孩,就跟我CP吧」

想也知道是你長得太醜…噢不,是聖誕老人長得太帥了才會有如此勁爆的發言。
前面的故事不怎麼重要,重要的是街上目前佈滿了一堆CP,而你理所當然地仇視他們。為了方便起見,你將圍繞在聖誕樹們的人們從$1$到$N$編號,以找出那些藏匿在人群中的可惡CP。

縱使那些CP和一般人一樣在呼吸,心臟也不曾停下,但恨透了CP的你卻能一眼看穿一個人是不是CP。你以0.001026秒將四周的人掃瞄過一遍,發現了一件有趣的事實:所有編號是平方數而且大於1的人,都是CP狗(你問我為什麼$1$不是CP嗎?那還用問,你就是一號啊),而且所有CP狗的編號一定是大於1的平方數。在鎖定了目標之後,你偷偷拿出預備好的鐵球們,朝著他們的身體猛力一丟(力氣真大),於是乎CP狗們都歸西了。然而你並沒有好好控制力道,所以鐵球們繼續反彈(?),彈死了所有編號是某個CP狗編號的倍數的人。

為了維持世界的平衡,你需要召喚替代品以維持人數守恆。然而你波及的範圍實在太大了,沒辦法一下就算出有幾個人被彈死了,因此你決定用程式解決這個問題。

Input Format

輸入只包含一行,包含一個正整數$N\leq 10^ {12}$.
對於30%的測資,$N\leq 10^ 6$

Output Format

請輸出一個數,代表你丟死或彈死的人的總數。

Sample Input

10

Sample Output

3

Hints

其實這題也是CP狗

Problem Source

Möbius Function
Problem set / Description by Paupière

Subtasks

For Testdata: 0 ~ 1, Score: 30
For Testdata: 2 ~ 4, 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