posts - 2,comments - 1,trackbacks - 0
#include<iostream>
#include
<vector>
using namespace std;

const int N = 100000;
const int mol = 20090531;

int a[N], p[N/10];
int p_fac[10], p_cnt[10], p_k;
int pf1[10], pc1[10], pk1; 

int ans, m;

int prime2( int n)
{
    
int i, j, k, t;
    
for ( i = 2 , k = 0 ; i < n ; i ++ )
    {
        
if!a[i] )
            p[ k 
++ ] = a[i] = i;
        
for ( j = 0 ; j < k ; j ++ )
        {
            t 
= p[j] * i;
            
if ( t >= n )
                
break;
            a[ t ] 
= p[ j ];
            
if( i % p[j] == 0 )
                
break;
        }
    }
    
return k;
}

// 要求 n > 1 
void fac_break( int n, int p_fac[], int p_cnt[], int &p_k )
{
    
if( n < N ){
        
int t ;
        p_k 
= p_cnt[ 0 ] = 0;
        
while( n != 1 )
        {
            t 
= p_fac[ p_k ] = a[n];
            
while( n % t == 0 )
            {
                n 
/= t , p_cnt[ p_k ] ++ ;
            }
            p_k 
++;
            p_cnt[ p_k ] 
= 0;
        }
    }
    
else
    {
        p_k 
= p_cnt [ 0 ] = 0;
        
for ( int i = 2 ; i * i <= n ; i ++ )
        {
            
if( n % i == 0 )
            {
                p_fac[ p_k ] 
= i;
                
while ( n % i == 0 )
                {
                    p_cnt [ p_k ] 
++;
                    n 
/= i;
                }
                p_k 
++;
                p_cnt[ p_k ] 
= 0;
            }
        }
        
if( n != 1 ){
            p_fac[ p_k ] 
= n; 
            p_cnt[ p_k 
++ ] = 1;
        }
    }
}

int ruler( int n)
{
    fac_break( n , p_fac, p_cnt, p_k );
    
for ( int i = 0 ; i < p_k ; i ++ ){
        n 
/= p_fac[ i ];
        n 
*= p_fac[ i ] - 1;
    }
    
return n;
}

int mol_pow( int a, int b )
{
    
int t = a, ans = 1;
    
while( b ){
        
if( b & 1 ){
            ans 
= 1ll * ans * t % mol;
        }
        t 
= 1ll * t * t % mol;
        b 
>>= 1;
    }
    
return ans;
}

// 生成所有约数。 已经调用了 fac_break(); 
void make_div( int k, int val, int p_fac[], int p_cnt[], const int &p_k, const int &n,const int &m ){
    
if( k == p_k ){
        
        
int t = ruler( n / val );
        ans 
= ( 1ll * t * mol_pow( m, val ) % mol + ans ) % mol;
        
        
return ;
    }
    
int t = 1;
    
for ( int i = 0 ; i <= p_cnt[ k ] ; i ++ )
    {
        make_div( k 
+ 1, val * t , p_fac, p_cnt, p_k, n, m );
        t 
*= p_fac[ k ];
    }
}

int ext_gcd( int a,int b,int &x,int &y)
{
    
if( b == 0 )
    {
        x 
= 1, y = 0;
        
return a;
    }
    
else
    {
        
int d = ext_gcd( b, a%b, x, y );
        
int t = x;
        x 
= y;
        y 
= t - a/b*y;
        
return d;
    }
}

int ni( int n )
{
    
int x, y;
    ext_gcd( n, mol, x, y );
    x 
%= mol;
    
if( x < 0 )
        x 
+= mol;
    
return x;
}

int main()
{
    prime2( N );
    
int i, j, k, n;
    
int test ;
    scanf(
"%d",&test);
    
while( test -- )
    {
        scanf(
"%d",&n);
        m 
= n;
        ans 
= 0;
        fac_break( n, pf1, pc1, pk1 );
        make_div( 
01 , pf1, pc1, pk1, n, m );
        
if( n % 2 ){
            ans 
= ( 1ll * n * mol_pow( m, n/2 + 1 ) % mol + ans ) % mol ;
        }
        
else{
            ans 
= ( 1ll * n / 2 * mol_pow( m, n/2 + 1 ) % mol + 1ll * n / 2 * mol_pow( m, n / 2 ) % mol + ans ) % mol ;
        }
        
//ni( n * 2 );
        ans = 1ll*ans*ni(n*2%mol)%mol;
        printf(
"%d\n",ans);
    }
    
return 0;
}

posted on 2009-08-19 15:16 Huicpc217 阅读(149) 评论(0)  编辑 收藏 引用 所属分类: 数论

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