你找到了在櫻花樹下哭泣的夏梨。(詳情請見TOIJ 1874)
你,妹可,今天也努力的想變成溫拿。
「喔膩醬...」
「夏梨,對不起...我不應該那麼做的...這都是我不對,請妳原諒我。」
「不,這不是喔膩醬的錯,一定是夏梨對喔膩醬太壞了,喔膩醬才會想要跟別的女生定下契約...」
「絕對沒有這回事!!其實,我對夏梨...我對妳...」
這時,你發現了異樣。
「吶,喔膩醬...」是櫻。「明明重複了這麼多次,為甚麼喔膩醬還是不懂...為甚麼喔膩醬你還要...拋棄我...」
瞬間,大地振動,天空變成灰色的,周圍出現了很多的飄散的櫻花花瓣,可是卻是黑色的。
「櫻,妳到底是誰?」
「我是喔膩醬在今天認識的女生喔。」
「妳...想對喔膩醬做甚麼!」夏梨擋在了你的面前保護你。
「我只不過像想要讓時間到轉而已...直到喔膩醬選擇我!!!」櫻的話一說完,你的眼前徒然一片黑暗。
但是你也不是省油的燈,你馬上使出了防禦魔法(你這半年也沒有在浪費時間,和夏梨學了一些魔法)。
你的腦中浮現了一堆數字,你必須找出一些數字來破除櫻的咒語。
你一定知道,要反制一些咒語必須要用一些相剋的能量來反制,而最好的作法就是找出和他互質的能量!!
由於你是小魯蛇,小魯蛇的魔法不可能比金髮小蘿莉強,所以你能選擇的只有小於等於櫻的能量的魔法。
時間不夠了,你決定寫個程式找出你能夠使用的魔法的個數。
這題有多筆輸入,讀到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 ,保證A為質數
對於每個櫻的法力A,你想要知道一個整數,代表小於等於A而且和A互質的數字的個數。
傳說中,歐拉曾經找出一個函數,可以解決這個問題,叫作歐拉函數,所以我們可以合理懷疑歐拉也遇過跟妹可一樣的狀況。
Step5 0084 神祕題
2015年建中校內培訓第七次模擬賽
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 1 |
2 | 1 | 2 |
3 | 2 | 4 |
4 | 3 | 8 |
5 | 4 | 16 |
6 | 5 | 32 |
7 | 6 | 37 |