#define farey_Max 100001
int farey_Size; //Fn的n
__int64 farey_Total; //farey序列元素个数
int farey[farey_Max][2]; //保存farey序列
//构造Farey序列
void MakeFarey( int x1, int y1, int x2, int y2 ){ //初始为0,1,1,1
if( y1+ y2> farey_Size ) return;
MakeFarey( x1, y1, x1+x2, y1+y2 );
farey[farey_Total][0]= x1+x2;
farey[farey_Total][1]= y1+y2;
farey_Total++;
MakeFarey( x1+x2, y1+y2, x2, y2 );
}
__int64 phy[farey_Max]; //欧拉函数
__int64 tab[farey_Max]; //|Fn|大小
//计算farey序列的元素个数
void FareyCount(){
int prime[200], size= 0;
bool comp[1000];
memset(comp,0,sizeof(comp));
phy[1] = 1;
tab[1] = 0;
prime[0] = 2;
int i, j, k;
//求素数
for( i= 2; i< 1000; i++ )
if( !comp[i] )
for( j= i+ i; j< 1000; j+= i )
comp[j]= 1;
for( i= 2; i< 1000; i++ )
if( !comp[i] )
prime[size++] = i;
//求欧拉函数
for( j= 2; j< farey_Max; j++ ){
for( i= 0; i< size ;i++ ){
if( j% prime[i]== 0 ){
k= j/ prime[i];
if( k%prime[i]== 0 )
phy[j]= phy[k]* prime[i];
else
phy[j]= phy[k]* (prime[i]-1);
break;
}
}
if( i== size )
phy[j]= j- 1;
}
//求序列个数
for( i= 2; i< farey_Max; i++ )
tab[i]= tab[i-1]+ phy[i];
}posted on 2009-03-17 22:15
古月残辉 阅读(831)
评论(0) 编辑 收藏 引用 所属分类:
Template