http://poj.org/problem?id=2154

楼爷的题目,题目大意就是一个长度为n的项链,首尾相接,用n种颜色去染色,求有多少种染色方案(经过旋转之后一样的,算同一种方案),最后只要输出总方案 mod P。
解法:polya定理  
由于n很大,所以对n进行分解之后,再DFS求出所有的因数。

  1/*
  2*    author: wwb
  3*    time: 2011/2/26  19:55
  4*   
  5*/

  6#include <cstdio>
  7#include <complex>
  8#include <cstdlib>
  9#include <iostream>
 10#include <cstring>
 11#include <string>
 12#include <algorithm>
 13using namespace std;
 14
 15const int maxn = 32000;
 16int vis[ maxn ], p[ maxn ];
 17int a[ 32 ], b[ 32 ];
 18int plen, flen;
 19
 20void prime( )
 21{
 22    int i, j, k;
 23    plen = 0;
 24    memset( vis, 0sizeof( vis ) );
 25    for( i = 2, k = 4; i < maxn; ++i, k += i + i - 1 )
 26    {
 27        if!vis[ i ] )
 28        {
 29            p[ plen++ ] = i;
 30            if( k < maxn ) for( j = k; j < maxn; j += i ) vis[ j ] = 1;
 31        }

 32    }

 33}

 34
 35void factor( int n )
 36{
 37    flen = 0;
 38    forint i = 0; p[ i ] * p[ i ] <= n; i++ )
 39    {
 40        if( n % p[ i ] == 0 )
 41        {    
 42            for( b[ flen ] = 0; n % p[ i ] == 0++b[ flen ], n /= p[ i ] );
 43            a[ flen++ ] = p[ i ];
 44        }

 45    }

 46    if( n > 1 ) b[ flen ] = 1, a[ flen++ ] = n;
 47}

 48
 49int elur( int n )
 50{
 51    int phi = n;
 52    forint i = 0; p[ i ] * p[ i ] <= n; i++ )
 53    {
 54        if( n % p[ i ] == 0 )
 55        {
 56            while( n % p[ i ] == 0 ) n /= p[ i ];
 57            phi -= phi / p[ i ];
 58        }

 59    }

 60    if( n > 1 ) phi -= phi / n;
 61    return phi;
 62}

 63
 64int ans, n, P;
 65
 66int pow_mod( int a, int b, int c )
 67{
 68    int ans = 1, d = a % c;
 69    while( b )
 70    {
 71        if( b & 1 ) ans = ans * d % c;
 72        d = d * d % c;
 73        b >>= 1;
 74    }

 75    return ans;
 76}

 77
 78void DFS( int dep, int sum )
 79{
 80    if( dep == flen )
 81    {
 82        ans = ( ans + elur( n / sum ) % P * pow_mod( n, sum - 1, P ) % P ) % P;
 83        return;
 84    }

 85    forint i = 0, tmp = 1; i <= b[ dep ]; tmp *= a[ dep ], i++ )
 86        DFS( dep + 1, sum * tmp );
 87}

 88
 89int main(int argc, char *argv[])
 90{
 91    int cas;
 92    prime( );
 93    scanf( "%d"&cas );
 94    while( cas-- )
 95    {
 96        scanf( "%d %d"&n, &P );
 97        factor( n );
 98        ans = 0;
 99        DFS( 01 );
100        printf( "%d\n", ans );
101    }

102    return 0;
103}

104