ACM – Uva10294 – 置换 -

项链和手镯。

项链的问题在于不可以翻转，因此少了一种置换，而手镯则可以反转。然后我们计算旋转的置换。

旋转的步长可以是0,i,2i…然后我们可以得出循环一共有n/gcd(i,n)个元素，因此，我们可以计算出一共有gcd(i,n)个循环。则不定点的个数为

$a = \Sigma t^{gcd(i,n)}$。

翻转。翻转奇数情况和偶数情况是不一样的，因为奇数情况会多一个不定点，这个不定点就是在轴上的点。剩余的不定点的个数就是$n/2$，总共不定点的个数就是$nt^{(n+1)/2}$。偶数的情况下，如果正好切在两个珠子上，那么循环长度为2的点有$n/2-1$个，长度为1的循环有2个，所以总共$n/2+1$个。如果没有切在珠子上，不定点的个数为$n/2$，和为$b = n/2*(t^{n/2+1} + t^{n/2})$。

然后我们可以计算出项链的个数$a/n$，手镯的个数$(a+b)/2n$

列出式子以后代码就方便了。记得求pow的时候可以顺手打表

/*=============================================================================
#
# Author: svtter - [email protected]
#
# QQ : 57180160
#
# Last modified: 2015-05-03 18:48
#
# Filename: 10294.cpp
#
# Description: 
#
=============================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define CR printf("\n")
const double PI = acos(-1.0);
int gcd(int a, int b)
{
    return b ==  ? a : gcd(b, a%b);
}
const int maxn = 60;
ll po[maxn];
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int n, t;
    ll ans, ans2;
    while(scanf("%d%d", &n, &t) != EOF && n)
    {
        po[] = 1;
        ans = ;
        for(int i = 1; i <= n; i++) po[i] = po[i-1] * t;
        for(int i = ; i < n;i++) ans += po[gcd(i, n)];
        ans2 = ans;
        if(n & 1) ans2 += n*po[(n+1)/2];
        else ans2 += n/2*(po[n/2+1] + po[n/2]);
        printf("%lld %lld\n", ans/n, ans2/(2*n));
    }
    return ;
}