扯回正题，此题需要知道的是置换群的概念，这点在刘汝佳的书中写的比较详细，此处不多做赘述。此处多说一句的是第二种手镯的情况。在下图中“左图顺时针转1个位置”和“右图顺时针旋转5个位置”是相同的，所以在最终结果处需要(ans1+ans2)/2。
可以看刘汝佳白书，来看，这道题，burnside引理和polya定理的经典应用。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std; int n,m;
ll a[]; int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
a[]=;
for (int i=;i<=n;i++)
a[i]=a[i-]*m;
ll x=,y=;
for (int i=;i<=n;i++)
x+=a[gcd(i,n)];
if (n%==) y=a[(n+)/]*n;
else y=(a[n/]+a[n/+])*n/;
printf("%lld %lld\n",x/n,(x+y)//n);
}
}