Necklace of Beads

// File Name: poj1286.cpp  
// Author: bo_jwolf  
// Created Time: 2013年10月07日 星期一 21:31:08  
  
#include<vector>  
#include<list>  
#include<map>  
#include<set>  
#include<deque>  
#include<stack>  
#include<bitset>  
#include<algorithm>  
#include<functional>  
#include<numeric>  
#include<utility>  
#include<sstream>  
#include<iostream>  
#include<iomanip>  
#include<cstdio>  
#include<cmath>  
#include<cstdlib>  
#include<cstring>  
#include<ctime>  
  
#define INT long long int  
  
using namespace std;  
INT gcd( INT a, INT b){  
    return b == 0? a: gcd( b, a % b );  
}  
  
INT c = 3, s;  
INT polya(){  
    INT ans = 0;  
    for( INT i = 0; i < s; ++i ){  
        ans += (INT)pow( 1.0 * c, gcd( s, i ) );  
    }  
    if( s % 2 ){  
        ans += s * ( INT )pow( 1.0 * c, ( s / 2 + 1 ) );  
    }  
    else{  
        ans += s / 2 * ( INT )pow( 1.0 * c, s / 2 );  
        ans += s / 2 * ( INT )pow( 1.0 * c, s / 2 + 1 );  
    }  
    return ans / 2 / s;  
}  
  
int main(){  
    INT ans;  
    while( scanf( "%lld", &s ) != EOF ){  
            if( s == -1 )  
                break;  
            if( s == 0 )  
                ans = 0;  
            else  
                ans = polya();  
            printf( "%lld\n", ans );  
    }  
return 0;  
}  

补充：软件开发 , C++ ,

上一个：(组合数学3.1.1.1)POJ 1146 ID Codes(字典序法)
下一个：Let it Bead