http://162.105.81.212/JudgeOnline/problem?id=1286本人第一道polya的题目，polya的入门题，看过polya的应该都没什么问题的。
1
#include<iostream>
2using namespace std;
3typedef __int64 ll;
4
int gcd( int a, int b )
{ return b ? gcd( b, a % b ) : a; }
5ll pow( ll a, ll n )
6{
7
ll ans = 1, d = a;
8 while( n )
9
{
10 if( n & 1 ) ans = ans * d;
11 d *= d;
12 n >>= 1;
13
}
14 return ans;
15
}
16
17ll solve( int n )
18{
19 int i;
20 ll sum = 0;
21 if( n == 0 )return 0;
22 for( i = 1; i <= n; i++ )
23 sum += pow( 3, gcd( i, n ) );
24 if( n % 2 == 0 )
25 {
26 sum += pow( 3, n / 2 ) * n / 2;
27 sum += pow( 3, n / 2 + 1 ) * n / 2;
28 }
29 else sum += pow( 3, n / 2 + 1 ) * n;
30 return sum / n / 2;
31}
32
33int main( )
34{
35 int n;
36 while( scanf("%d",&n) && n != -1 )
37 {
38 printf("%I64d\n",solve( n ));
39 }
40 return 0;
41}