http://acm.hdu.edu.cn/showproblem.php?pid=2865

题意：AekdyCoin大神对一个特殊的玩具进行染色，跟pku2888（http://www.cppblog.com/AmazingCaddy/archive/2011/02/27/140750.html）差不多。玩具如题中所示，中间一个圆，外面圆周上排列了N个小圆，形成一个大圈，一共N+1个圆，每个小圆都与大圆相连，一共可以用K种颜色，最后答案 mod 1000000007。

解法：又是polya计数。
           首先，由于中间一个大圆与每个小圆都相连，所以大圆用去一种颜色之后，只剩下K-1种颜色。
           设K-1种颜色染N个珠子的不同方案数为M，最后就是求M×K mod 1000000007。
           方法跟pku 2888一样，但是这次矩阵的规模很大，所以不能用矩阵来存这个图形了。
           但由于此处规定相邻珠子颜色不同， 则邻接阵为对角线上元素全为0,，其余元素全为1。
           该矩阵的幂的迹，可以推导出公式 ( p - 1 ) ^ n + ( -1 ) ^ n * ( p - 1 ) 其中p是矩阵的阶数，也就是K-1。

  1/*
  2    author: wwb
  3    time: 2011/2/27  17:38
  4*/
  5#include <cstdio>
  6#include <complex>
  7#include <cstdlib>
  8#include <iostream>
  9#include <cstring>
 10#include <string>
 11#include <algorithm>
 12using namespace std;
 13
 14typedef __int64 ll;
 15const ll P = 1000000007;
 16const int maxn = 32000;
 17
 18int vis[ maxn ], p[ maxn ];
 19int a[ 32 ], b[ 32 ];
 20int plen, flen;
 21int N, K;
 22ll ANS;
 23
 24void prime( )
 25{
 26    int i, j, k;
 27    plen = 0;
 28    memset( vis, 0, sizeof( vis ) );
 29    for( i = 2, k = 4; i < maxn; ++i, k += i + i - 1 )
 30    {
 31        if( !vis[ i ] )
 32        {
 33            p[ plen++ ] = i;
 34            if( k < maxn ) for( j = k; j < maxn; j += i ) vis[ j ] = 1;
 35        }
 36    }
 37}
 38
 39int elur( int n )
 40{
 41    int phi = n;
 42    for( int i = 0; p[ i ] * p[ i ] <= n; i++ )
 43    {
 44        if( n % p[ i ] == 0 )
 45        {
 46            while( n % p[ i ] == 0 ) n /= p[ i ];
 47            phi -= phi / p[ i ];
 48        }
 49    }
 50    if( n > 1 ) phi -= phi / n;
 51    return phi;
 52}
 53
 54void factor( int n )
 55{
 56    flen = 0;
 57    for( int i = 0; p[ i ] * p[ i ] <= n; i++ )
 58    {
 59        if( n % p[ i ] == 0 )
 60        {
 61            for( b[ flen ] = 0; n % p[ i ] == 0; ++b[ flen ], n /= p[ i ] );
 62            a[ flen++ ] = p[ i ];
 63        }
 64    }
 65    if( n > 1 ) b[ flen ] = 1, a[ flen++ ] = n;
 66}
 67
 68ll pow_mod( ll a, ll b, ll c )
 69{
 70    ll ans = 1, d = a % c;
 71    while( b )
 72    {
 73        if( b & 1 ) ans = ans * d % c;
 74        d = d * d % c;
 75        b >>= 1;
 76    }
 77    return ans;
 78}
 79
 80ll Mod( ll a, ll b )
 81{
 82    return ( a % b + b ) % b;
 83}
 84
 85ll inv( ll n )
 86{
 87    return pow_mod( n, P - 2, P );
 88}
 89
 90ll Trace( int n, int col_num )
 91{
 92    ll a = col_num - 1;
 93    return Mod( pow_mod( a, n, P ) + ( n % 2 ? -1 : 1 ) * a, P );
 94}
 95
 96void DFS( int dep, int t )
 97{
 98    if( dep == flen )
 99    {
100        ANS = ( ANS + (ll)elur( t ) * Trace( N / t, K - 1 ) % P ) % P;
101        return;
102    }
103    for( int tmp = 1, i = 0; i <= b[ dep ]; tmp *= a[ dep ], i++ )
104        DFS( dep + 1, t * tmp );
105}
106
107int main(int argc, char *argv[])
108{
109    prime( );
110    while( scanf( "%d%d", &N, &K ) != EOF )
111    {
112        factor( N );
113        ANS = 0;
114        DFS( 0, 1 );
115        ANS = ANS * inv( N ) % P;
116        ANS = ANS * K % P;
117        printf( "%I64d\n", ANS );
118    }
119    return 0;
120}
121