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, 0, sizeof( 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    for( int 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    for( int 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    for( int 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( 0, 1 );
100        printf( "%d\n", ans );
101    }
102    return 0;
103}
104