hdu4556-Stern-Brocot Tree

[cpp]
#include<iostream>  
#include<cstdio>  
#include<cstring>  
 
using namespace std ; 
 
#define maxn 1000005  
#define INT __int64  
INT ans[ maxn + 1] ; 
void enlerfun() 
{ 
    memset( ans , 0 , sizeof( ans ) ); 
    ans[ 1 ] = 1 ; 
    for( int i = 2 ; i <= maxn ; ++i ) 
    { 
        if( !ans[ i ] ) 
        { 
            for( int j = i ; j <= maxn ; j += i ) 
            { 
                if( !ans[ j ] ) 
                    ans[ j ] = j ; 
                ans[ j ] = ans[ j ] / i * ( i - 1 ) ; 
            } 
        } 
        ans[ i ] += ans[ i - 1 ] ; 
    } 
} 
 
int main() 
{ 
    int n ; 
    enlerfun() ; 
    while( scanf( "%d" , &n ) != EOF  && n ) 
    { 
        printf( "%I64d\n" , 2 * ans[ n ] + 1 ) ; 
    } 
    return 0 ; 
} 

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std ;

#define maxn 1000005
#define INT __int64
INT ans[ maxn + 1] ;
void enlerfun()
{
 memset( ans , 0 , sizeof( ans ) );
 ans[ 1 ] = 1 ;
 for( int i = 2 ; i <= maxn ; ++i )
 {
  if( !ans[ i ] )
  {
   for( int j = i ; j <= maxn ; j += i )
   {
    if( !ans[ j ] )
     ans[ j ] = j ;
    ans[ j ] = ans[ j ] / i * ( i - 1 ) ;
   }
  }
  ans[ i ] += ans[ i - 1 ] ;
 }
}

int main()
{
 int n ;
 enlerfun() ;
 while( scanf( "%d" , &n ) != EOF  && n )
 {
  printf( "%I64d\n" , 2 * ans[ n ] + 1 ) ;
 }
 return 0 ;
}