本文共 1437 字，大约阅读时间需要 4 分钟。

题目链接：

此题题解 不太懂，因为对这些概念，定理太模糊，理解起来比较困难，不过想想还是应该把代码写出来；

题意：给你一个数 n ，代表 n 种颜色和n个珠子，问你可以组合多少种长度为n的项链；不需要用掉n种颜色，项链的旋转和翻转都是为同一条

题解： 

点进去之后点击C.ppt

公式：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;typedef long long LL;const LL mod = 20090531;LL x,y;LL euler(LL p)//欧拉定理{    LL res = p;    for(LL i = 2;i <= sqrt(p);i++)    {        if(p%i==0)        {            while(p%i==0) p/=i;            res = res/i*(i-1);        }    }    if(p > 1) res = res / p * (p-1);    return res%mod;}LL fast_pow(LL a,LL b)//快速幂{    LL res = 1;    while(b)    {        if(b&1) res = (res * a) % mod;        a = (a * a) % mod;        b >>= 1;    }    return res;}void edgcd(LL a,LL b)//求逆元{    if(b == 0)    {x = 1;y = 0;return;}    edgcd(b,a%b);    LL temp = x;    x = y;y = temp - a/b*y;}void solve(LL m){    LL res = 0;    for(LL i = 1;i <= sqrt(m);i++)    {        if(m%i==0)        {            if(m/i != i) res = (res + euler(i)*fast_pow(m,m/i-1))%mod;            res = (res + euler(m/i)*fast_pow(m,i-1))%mod;        }    }    if(m&1)    {        res = (fast_pow(m,(m+1)/2) + res) % mod;        edgcd(2,mod);    }    else    {        res = (fast_pow(m,m/2+1) + fast_pow(m,m/2) + 2 * res) % mod;        edgcd(4,mod);    }    while(x < 0) x = (x + mod) % mod;    printf("%lld\n",x * res % mod);}int main(){    int n;    LL m;    scanf("%d",&n);    while(n--)    {        scanf("%lld",&m);        solve(m);    }}