首页 > 代码库 > POJ 2478 Farey Sequence( 欧拉函数 + 法雷数列 )

POJ 2478 Farey Sequence( 欧拉函数 + 法雷数列 )

 

 

POJ 2478 Farey Sequence ( 欧拉函数 + 法雷数列 )

 

 

 

#include <cstdio>#include <cstring> using namespace std;#define MAXN 1000005typedef long long LL;int vis[ MAXN ], prime[ MAXN ], cnt, n;LL phi[ MAXN ];void get_phi_prime( int N ){    phi[1] = 1;    cnt = 0;    for( int i = 2; i <= N; ++i )    {        if( !vis[i] )        {            prime[ cnt++ ] = i;            phi[i] = i - 1;        }        for( int j = 0; j < cnt; ++j )        {            if( i * prime[j] > N ) break;            vis[ i * prime[j] ] = 1;            if( i % prime[j] == 0 ){                phi[ i * prime[j] ] = phi[i] * prime[j];                break;            }            else                phi[ i * prime[j] ] = phi[i] * ( prime[j] - 1 );        }    }}void cal(){    for( int i = 3; i < MAXN; ++i )        phi[i] += phi[i - 1];}int main(){    get_phi_prime( MAXN );    cal();    while( ~scanf( "%d", &n ) && n )    {        printf( "%lld\n", phi[n] );    }    return 0;}
代码君

 

POJ 2478 Farey Sequence( 欧拉函数 + 法雷数列 )