번사이드 보조정리(회전 대칭 경우의 수) 계산기

대칭으로 겹치는 것을 하나로 셀 때 쓰는 공식입니다. 서로 다른 것의 개수는 각 대칭이 그대로 두는 배치 수의 평균, 즉 (1/|G|) × Σ(g가 고정하는 배치 수)입니다. 목걸이 색칠처럼 「돌리면 같은 것」을 세는 문제의 표준 도구입니다.

안 됩니다. 돌려도 자기 자신이 되는 배치가 있기 때문입니다. 전부 같은 색으로 칠한 목걸이는 아무리 돌려도 그대로라 n가지가 아니라 한 가지만 나옵니다. 그래서 나눈 값은 정수도 아니고 답보다 작습니다. 구슬 4개 2색이면 16 ÷ 4 = 4인데 실제 답은 6가지입니다.

d칸 돌리는 회전은 구슬을 gcd(d, n)개의 묶음으로 나눕니다. 한 묶음 안의 구슬이 모두 같은 색일 때만 배치가 그대로이므로 k^gcd(d,n)가지입니다. 이를 d = 0부터 n−1까지 더해 n으로 나눈 것이 목걸이의 개수입니다.

뒤집기를 같게 보느냐가 다릅니다. 목걸이는 돌리기만 같게 보아 군의 크기가 n이고, 팔찌는 뒤집기까지 같게 보아 2n입니다. 다만 뒤집는다고 개수가 반드시 줄지는 않습니다. 구슬 4개 2색은 목걸이와 팔찌가 둘 다 6가지입니다.

대칭축의 종류가 둘로 갈리기 때문입니다. 짝수면 구슬 둘을 지나는 축이 n/2개(묶음 n/2+1개), 변의 가운데 둘을 지나는 축이 n/2개(묶음 n/2개)입니다. 홀수면 모든 축이 구슬 하나와 맞은편 변의 가운데를 지나고 묶음이 (n+1)/2개로 하나뿐입니다. 이 홀짝 갈림이 가장 틀리기 쉬운 곳입니다.

페르마 소정리가 나옵니다. p가 소수면 그대로 두기 말고는 모든 회전이 gcd = 1이라 k가지씩만 남기므로 답이 (k^p − k)/p + k가 됩니다. 이 값이 정수라는 것은 곧 k^p − k가 p로 나누어떨어진다는 뜻입니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력한 값은 이 기기에만 남습니다.