随笔-20  评论-16  文章-36  trackbacks-0
#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 古月残辉 阅读(855) 评论(0)  编辑 收藏 引用 所属分类: Template

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理