首页 > 代码库 > 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( 欧拉函数 + 法雷数列 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。