题目链接：

题意：n个小圆组成的正n边形，中间有一个大圆。有木棍相连的两个圆不能有相同的颜色，旋转后相同视为相同的方案，求着色方案数。

思路：中间选一种颜色，剩下的是K-1种。设K=K-1。设f[n]表示n个小球的合法方案数。其中第一个和第n个的颜色不同。若第一个与第n-1个颜色相同，f[n]=f[n-2]*(K-1),否则f[n]=f[n-1]*(K-2)，所以f[n]=f[n-2]*(K-1)+f[n-1]*(K-2)。因此，枚举n的约数t，则ans=sigama(f[t]*eular(n/t))。

int n,K;class Matrix{public:    i64 a[N][N];    Matrix()    {        clr(a,0);    }    void init(int x)    {        if(x==0) a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;        else if(x==1) a[0][0]=a[1][1]=1,a[0][1]=a[1][0]=0;        else        {            a[0][0]=K-2;            a[0][1]=1;            a[1][0]=K-1;            a[1][1]=0;        }    }};Matrix operator*(Matrix &a,Matrix &b){    int i,j,k;    Matrix p;    p.init(0);    FOR0(i,2) FOR0(j,2) FOR0(k,2)    {        (p.a[i][j]+=a.a[i][k]*b.a[k][j]%mod)%=mod;    }    return p;}Matrix operator^(Matrix a,int t){    Matrix ans;    ans.init(1);    while(t)    {        if(t&1) ans=ans*a;        a=a*a;        t>>=1;    }    return ans;}Matrix a;int prime[M],tag[M],cnt;vector
     
       factor;void init(){    int i,j;    for(i=2;i<180;i++) if(!tag[i])    {        for(j=i*i;j
      
       1) ans=ans/n*(n-1);    return ans;}i64 exGcd(i64 a,i64 b,i64 &x,i64 &y){    if(!b)    {        x=1;y=0;        return a;    }    i64 r=exGcd(b,a%b,x,y);    i64 temp=x;    x=y;    y=temp-a/b*y;    return r;}i64 reverse(int a){    i64 x,y;    exGcd(a,mod,x,y);    x=(x%mod+mod)%mod;    return x;}i64 get(int n){    i64 ans=0;    if(n==1) ans=0;    else if(n==2) ans=(i64)K*(K-1)%mod;    else if(n==3) ans=(i64)K*(K-1)%mod*(K-2)%mod;    else    {        a.init(2);        a=a^(n-3);        ans+=a.a[0][0]*K%mod*(K-1)%mod*(K-2)%mod;        ans+=a.a[1][0]*K%mod*(K-1)%mod;    }    return ans%mod;}int main(){    init();    while(scanf("%d%d",&n,&K)!=-1)    {        K--;        split();        i64 ans=0;        int i;        FOR0(i,SZ(factor))        {            ans+=get(factor[i])*eular(n/factor[i])%mod;            if(ans>=mod) ans-=mod;        }        ans=ans*reverse(n)%mod*(K+1)%mod;        printf("%I64d\n",ans);    }    return 0;}