LightOJ 1419 – Necklace 用m个颜色去涂n个球（环状） 要求相邻可同色

题意：http://www.lightoj.com/volume_showproblem.php?problem=1419

输入n和m  表示有n个球  有m个颜色  相邻可以同色  有多少种情况   

Polya计数+费马小定理求逆元

但是我不会第一个   死记吧  

第二个就比较简单了 就是一个公式

a/b%mod=a*(b^(mod-2))%mod  表示a乘b的（mod-2）次方    mod是素数

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<math.h>
#include<string>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define N 10006
#define mod 1000000007
#define Lson rood<<1
#define Rson rood<<1|1
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
LL poww(LL a,LL b)
{
    LL c=1;
    while(b)
    {
        if(b&1) c=c*a%mod;
        b=b/2;
        a=a*a%mod;
    }
    return c;
}
int main()
{
    int T,t=1;
    scanf("%d",&T);
    while(T--)
    {
        LL n,m,sum=0;
        scanf("%lld%lld",&n,&m);
        for(LL i=0;i<n;i++)
        {
            LL t=gcd(n,i);
            sum=(sum+poww(m,t))%mod;
        }
        printf("Case %d: %lld
",t++,sum*poww(n,mod-2)%mod);
    }
    return 0;
}