//Euler 函數前n項和
/*
phi(n) 為n的Euler原函數
if( (n/p) ％ i == 0 ) phi(n)=phi(n/p)*i
else phi(n)=phi(n/p)*(i-1)
對于約數：divnum
如果i|pr[j] 那么 divnum[i*pr[j]]=divsum[i]/(e[i]+1)*(e[i]+2) //最小素因子次數加1
否則 divnum[i*pr[j]]=divnum[i]*divnum[pr[j]] //滿足積性函數條件
對于素因子的冪次 e[i]
如果i|pr[j] e[i*pr[j]]=e[i]+1 //最小素因子次數加1
否則 e[i*pr[j]]=1 //pr[j]為1次
對于本題：
1. 篩素數的時候首先會判斷i是否是素數。
根據定義，當 x 是素數時 phi[x] = x-1
因此這里我們可以直接寫上 phi[i] = i-1
2. 接著我們會看prime[j]是否是i的約數
如果是，那么根據上述推導，我們有：phi[ i * prime[j] ] = phi[i] * prime[j]
否則
phi[ i * prime[j] ] = phi[i] * (prime[j]-1)
(其實這里prime[j]-1就是phi[prime[j]]，利用了歐拉函數的積性)
經過以上改良，在篩完素數后，我們就計算出了phi[]的所有值。
我們求出phi[]的前綴和
*/
標簽：
phi
Euler
else
函數
上傳時間：
2016-12-31
上傳用戶：gyq
