TopCoder

Thumb 03
tangent
點心被吃掉啦OAO

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

70.6% (12/17)

Description

你找到了在櫻花樹下哭泣的夏梨。(詳情請見TOIJ 1874)

你,妹可,今天也努力的想變成溫拿。
「喔膩醬...」
「夏梨,對不起...我不應該那麼做的...這都是我不對,請妳原諒我。」
「不,這不是喔膩醬的錯,一定是夏梨對喔膩醬太壞了,喔膩醬才會想要跟別的女生定下契約...」
「絕對沒有這回事!!其實,我對夏梨...我對妳...」

這時,你發現了異樣。

「吶,喔膩醬...」是櫻。「明明重複了這麼多次,為甚麼喔膩醬還是不懂...為甚麼喔膩醬你還要...拋棄我...」
瞬間,大地振動,天空變成灰色的,周圍出現了很多的飄散的櫻花花瓣,可是卻是黑色的。
「櫻,妳到底是誰?」
「我是喔膩醬在今天認識的女生喔。」
「妳...想對喔膩醬做甚麼!」夏梨擋在了你的面前保護你。
「我只不過像想要讓時間到轉而已...直到喔膩醬選擇我!!!」櫻的話一說完,你的眼前徒然一片黑暗。

但是你也不是省油的燈,你馬上使出了防禦魔法(你這半年也沒有在浪費時間,和夏梨學了一些魔法)。
你的腦中浮現了一堆數字,你必須找出一些數字來破除櫻的咒語。

你一定知道,要反制一些咒語必須要用一些相剋的能量來反制,而最好的作法就是找出和他互質的能量!!
由於你是小魯蛇,小魯蛇的魔法不可能比金髮小蘿莉強,所以你能選擇的只有小於等於櫻的能量的魔法。

時間不夠了,你決定寫個程式找出你能夠使用的魔法的個數。

Input Format

這題有多筆輸入,讀到EOF結束。(不會超過20筆測資)
每行有一個整數A代表櫻的法力。

測資組A : 1≤N≤1
測資組B : 1≤N≤20
測資組C : 1≤N≤300
測資組D : 1≤N≤40000
測資組E : 1≤N≤5000000
測資組F : 1≤N≤600000000
測資組G : 1≤N≤7×1018 ,保證x為質數

Output Format

對於每個櫻的法力A,你想要知道一個整數,代表小於等於A而且和A互直的數字的個數。

Sample Input

1
1111111111093

Sample Output

1
1111111111092

Hints

傳說中,歐拉曾經找出一個函數,可以解決這個問題,叫作歐拉函數,所以我們可以合理懷疑歐拉也遇過跟妹可一樣的狀況。

Problem Source

Step5 0084 神祕題
2015年建中校內培訓第七次模擬賽

Subtasks

For Testdata: 0 ~ 0, Score: 1
For Testdata: 1 ~ 1, Score: 2
For Testdata: 2 ~ 2, Score: 4
For Testdata: 3 ~ 3, Score: 8
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 32
For Testdata: 6 ~ 6, Score: 37
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536