P4980 【模板】Polya定理:


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=1000000007;
const int maxn=100100;
int prime[maxn];
int ha[maxn];
int cnt=0;
void Prime(void)
{
    ha[1]=true;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&prime[j]*i<maxn;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

int p[100],e[100];
int tot;

void only(int n)
{
    memset(e,0,sizeof(e));
    tot=0;
    for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]) continue;
        p[++tot]=prime[i];
        while(n%prime[i]==0)
        {
            n/=prime[i];
            e[tot]++;
        }
    }
    if(n>1) p[++tot]=n,e[tot]=1;
    return ;
}
int n;
ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int mypow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
ll ans=0;
vector<int>vc;

void DFS(int pos,int d)
{
    if(pos>tot)
    {
        ll pp=mypow((ll)n,(ll)n/d-1);
        for(int i=0;i<vc.size();i++)
            d=d-d/vc[i];
        ans=(ans+d*pp)%mod;
        return ;
    }
    for(int i=0;i<=e[pos];i++)
    {

        if(i>0) vc.push_back(p[pos]);
        DFS(pos+1,d*mypow(p[pos],i));
        if(i>0) vc.pop_back();
    }
}


int main(void)
{
    int t;
    scanf("%d",&t);
    Prime();
    while(t--)
    {
        scanf("%d",&n);
        vc.clear();
        int pp=n;
        only(pp);
        ans=0;
        DFS(1,1);
        printf("%lld\n",ans);
    }
    return 0;
}