学步园

题解：

E(x)表示比x小的且与x互质的正整数的个数。

1.若p是素数，E(p)=p-1。
2.E(p^k)=p^k-p^(k-1)=(p-1)*P^(k-1)
证：令n=p^k,小于n的正整数数共有n-1即(p^k-1)个,其中与p不质的数共[p^(k-1)-1]个(分别为1*p,2*p,3*p...p(p^(k-1)-1))。所以E(p^k)=(p^k-1)-(p^(k-1)-1)=p^k-p^(k-1).得证。

3.若ab互质，则E(a*b)=E(a)*E(b)，欧拉函数是积性函数.
由于对任意数n都可以唯一分解成n=p1^a1*p2^a2*p3^a3*...*pn^an(pi为素数).
则 E(n)=E(p1^a1)*E(p2^a2)*E(p3^a3)*...*E(pn^an)     
      =(p1-1)*p1^(a1-1)*(p2-1)*p2^(a2-1)*...*(pn-1)*pn^(an-1)
      =(p1^a1*p2^a2*p3^a3*...*pn^an)*[(p1-1)*(p2-1)*(p3-1)*...*(pn-1)]/(p1*p2*p3*...*pn)
      =n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)

E(p^k)    =(p-1)*p^(k-1)=(p-1)*p^(k-2)*p
E(p^(k-1))=(p-1)*p^(k-2)
当k>1时，E(p^k)=E(p*p^(k-1))=E(p^(k-1))*p.     
由上式: 设P是素数，
若p是x的约数，则E(x*p)=E(x)*p.
若p不是x的约数，则E(x*p)=E(x)*E(p)=E(x)*(p-1).  ----由欧拉函数的积性可得，当k=1时，E(p)=p-1. 

#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 1000001
int p[MAX], a[MAX], pn;
__int64 eul[MAX];

void prime()
{
    pn = 0;
    memset(a,0,sizeof(a));
    int i, j;
    for ( i = 2; i < MAX; i++ )
    {
        if ( a[i] == 0 ) p[pn++] = i;
        for ( j = 0; j < pn && i * p[j] < MAX && (p[j] <= a[i] || a[i] == 0); j++ )
            a[i*p[j]] = p[j];
    }
}

void Farey ()
{
    for ( int i = 2; i < MAX; i++ )
    {
        if ( a[i] == 0 )
            eul[i] = i - 1;
        else
        {
            int k = i / a[i];
            if ( k % a[i] == 0 ) eul[i] = eul[k] * a[i];
            else eul[i] = eul[k] * ( a[i] - 1 );
        }
    }

    for ( int i = 3; i < MAX; i++ )
        eul[i] += eul[i-1];
}

int main()
{
    int n;
    prime(); Farey();
    while ( scanf("%d",&n) && n )
        printf("%I64d\n",eul[n]);
    return 0;
}