f588: 數字D×D 番外篇
Tags : math 數學
Accepted rate : 1人/2人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-01-01 20:59

Content

終於到可以交卷的時間
一誠交完考卷後,就收拾書包準備回家
這時老師說:先別那麼急嘛,給你一個回家作業
一誠:什麼回家作業?
老師:給你一個數字N,請問有多少數字小於N並且和N互質
一誠:阿不就歐拉函數?
老師:阿那個...剛剛是你聽錯了,我要問的是φ(1)+φ(2)+...+φ(N-1)+φ(N)為多少 φ()代表歐拉函數

Input

第一個數字T代表有幾筆測資(T<=10)
接下來T行每行有一個數字N(N<2^31)
聽說和數字D×D 續的測資一樣

Output

φ(1)+φ(2)+...+φ(N-1)+φ(N)為多少

Sample Input #1
5
1
2
3
4
39
Sample Output #1
1
2
4
6
474
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.0s , <1K
不公開 測資點#8 (10%): 1.0s , <1K
不公開 測資點#9 (10%): 1.0s , <1K
Hint :

O(N2/3)

Tags:
math 數學
出處:
[管理者:
DE45A (一葉之秋)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」