UVA11426 欧拉函数

时间:2021-07-01 19:16:20

大白书P125

 #include <iostream>
#include <cstring>
using namespace std;
#define MMX 4000010
#define LL long long
int phi[MMX],f[MMX];
LL S[MMX]; void calc_phi(int n) //求1--n的欧拉函数,phi[i]=φ(i)
{
for (int i=;i<=n;i++)
phi[i]=;
phi[]=;
for (int i=;i<=n;i++)
if (!phi[i])
for (int j=i;j<=n;j+=i)
{
if (!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
} int main()
{
calc_phi(MMX);
memset(f,,sizeof(f));
for (int i=;i<=MMX;i++)
for (int j=*i;j<=MMX;j+=i)
f[j]+=i*phi[j/i]; S[]=f[];
for (int i=;i<=MMX;i++)
S[i]=S[i-]+f[i]; int n;
while (cin>>n)
{
if (n==) break;
cout<<S[n]<<endl;
}
}