poj2409

用n个颜色的珠子编项链,求有多少种情况

由N(G,C) = 所有f的稳定核的和/|G|

m边形有m种旋转m种翻转

首先说旋转,有模线性方程可知每种旋转都有gcd(m,i)个循环节且每个循环节长度为n/gcd(m,i)

所以每个旋转的稳定核 = pow(n,gcd(m,i))

翻转的循环节数可有观察得知

#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<cmath>
#include<iostream>
using namespace std;
#define ll long long
int main(){
//freopen("in.cpp", "r", stdin);
ll ans;
int n, m;
while(scanf("%d%d", &n, &m), n+m){
ans = ;
ll sum = ;
for(int i =; i <= m; i++){
sum += pow(n, __gcd(i, m));
}
ans = sum;//cout<<"*"<<ans<<endl;
if(m & ){
sum = ;
for(int i = ; i < (m+)/; i++){
sum *= n;
}
sum *= m;
ans += sum;
}else{
sum = ;
for(int i = ; i < m/; i++){
sum *= n;
}
ans += m/*(sum + sum*n);
}//cout<<ans<<endl;
ans/= m*;
cout<<ans<<endl;
}
}
上一篇:POJ 1701


下一篇:why app_start start