题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3923
一道标准的Pólya定理(不懂Pólya定理的欢迎观看小编另一篇博客)问题。
题目意思是给我们n个小球，求用m种颜色在一个圈上排列的方法数，我们只需要列举出每一种置换的循环节个数就好。
1.旋转：
旋转的方法有n种，每一种的循环节个数为gcd(n,i)(0<=i<=n)。
2.翻转：
翻转要分情况：
(1)n为奇数：当n是奇数时只有一种翻折方式，沿着一个点和对边的中点翻折。循环节个数为(n-1)/2+1.
(2)n为偶数：当n为偶数的时候有两种翻折方式，一个是沿着一个点和对边翻折，循环节为(n-2)/2+2，一个是沿着一条边的中点和对边的中点翻折，循环节是n/2.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long LL;
using namespace std;
const int MOD = 1000000007;
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
void exGcd(LL a,LL b,LL &x,LL &y)
{if(b == 0){x = 1;y = 0;return ;}exGcd(b, a%b, y, x);y -= x*(a/b);
}
LL Power_mod(LL a,LL b)
{LL ans = 1;while(b){if(b&1) ans = (ans*a)%MOD;a = (a*a)%MOD;b >>= 1;}return ans;
}
LL flip(LL n,LL m)
{LL ans;if(n&1)return (Power_mod(m,n/2+1)*n)%MOD;else{ans = (Power_mod(m,n>>1)*(n>>1))%MOD;ans = (ans+(Power_mod(m,n/2+1)*(n>>1)))%MOD;return ans;}
}
LL spin(LL n,LL m)
{int i;LL ans = (Power_mod(m,n))%MOD;for(i=1;i<n;i++)ans = (ans+Power_mod(m,gcd(n,i)))%MOD;return ans;
}
int main()
{int T,t=1;LL n,m;scanf("%d",&T);while(T--){LL ans;scanf("%I64d%I64d",&m,&n);ans=flip(n, m);ans+=spin(n, m);LL x,y;exGcd(n*2, MOD, x, y);ans = (ans*((x+MOD)%MOD))%MOD;printf("Case #%d: %I64d\n",t++, ans);}return 0;
}