莫比乌斯函数

和容斥有点相似，代码看懂了，原理还不是很理解。

ll mod_pow(ll x,ll n,ll mod)
{
    ll res = 1;
    while(n > 0)
    {
        if(n & 1) res = (res * x)%moder;
        x = (x*x)%moder;
        n >>= 1;
    }
    return res;
}



map<int,int> moebius(int n)
{
    map<int,int>res;
    vector<int>primes;

    for(int i=2;i*i < n;i++)
    {
        if(n%i == 0)
        {
            primes.push_back(i);
            while(n%i ==0) n = n/i;
        }
    }
    if(n != 1)primes.push_back(n);

    int m = primes.size();
    for(int i=0;i < (1 << m);i++)
    {
        int mu=1,d=1;
        for(int j=0;j < m;j++)
        {
            if(i << j & 1)
            {
                mu *= -1;
                d *= primes[j];
            }
        }
        res[d] = mu;
    }
    return res;
}

int n;
void solve()
{
    int res = 0;
    map<int,int> mu = moebius(n);
    for(map<int,int>::iterator it = mu.begin();it != mu.end();++it)
    {
        res += it->second * mod_pow(26,n/it->first,moder);
        res = (res%moder+moder)%moder;
    }
    printf("%d
",res);
}

——