POJ - 1286 Necklace of Beads——Polya

POJ - 1286 Necklace of Beads——Polya

裸的Polya

注意n可能是0，不处理的话最后/0会RE

#include #include #include #include using namespace std;typedef long long ll;ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }ll ipow(ll a, int n) { ll ans = 1; while (n) { if (n & 1) ans *= a; a *= a; n >>= 1; } return ans;}int main() { int n; while (~scanf("%d", &n) && ~n) { if (n == 0) { printf("0\n"); continue; } ll ans = 0; for (int i = 0; i < n; i++) ans += ipow(3, gcd(i, n)); if (n & 1) ans += n * ipow(3, (n+1)/2); else { ans += n/2 * ipow(3, (n+2)/2); ans += n/2 * ipow(3, n/2); } ans /= (2 * n); printf("%lld\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。