ybtoj 43.B 周期字符串

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e8+5;
const int mod=1e9+7;
int n;
int mu(int x)
{
    int res=1;
    for(int i=2;1LL*i*i<=x;i++)
    {
        if(x%i!=0) continue;
        int cnt=0;
        while(x%i==0) x/=i,cnt++;
        if(cnt>=2) return 0;
        res*=-1;
    }
    if(x>1) res*=-1;
    return res; 
}
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=1LL*res*a%mod;
        a=1LL*a*a%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    scanf("%d",&n);
    int lim=sqrt(n);
    int ans=0;
    for(int i=1;i<=lim;i++)
    {
        if(n%i!=0) continue; 
        ans=(ans+1LL*qpow(26,i)*mu(n/i)%mod+mod)%mod;
        if(i*i!=n) ans=(ans+1LL*qpow(26,n/i)*mu(i)%mod+mod)%mod;
    }
    printf("%d",(ans+mod)%mod);
    return 0;
}