2019-05-21 莫比乌斯反演函数

//把n的约数的莫比乌斯函数值使用map的形式返回
map<int,int> moebius(int n){
    map<int,int>res;
    vector<int>primes;
    
    //枚举n的质因数
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            primes.push_back(i);
            while(n%i==0) 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;
    }
} 

const int MOD=10009;

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,MOD);
        res=(res%MOD+MOD)%MOD;
    } 
    printf("%d\n",res);
}