Mobius Function.cpp

/*
    CF 915G
*/

#define _CRT_SECURE_NO_DEPRECATE
#pragma comment(linker, "/STACK:167772160000")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define MAX 2000001
#define MOD 1000000007
vector<int> V[MAX];
bool prime[MAX];
int mu[MAX];
ll f[MAX], power[MAX];

void sieve()
{
    memset(prime, true, sizeof prime);
    for(int i=2; i<MAX; i++){
        mu[i] = 1;
    }
    for(int i=2; i<MAX; i++){
        if(mu[i] == 0) continue;
        if(prime[i]) mu[i] = mu[i]*-1;
        for(int j=2*i; j<MAX; j+=i){
            if((prime[i] == true)&& (j%(i*i) == 0)) mu[j] = 0;
            if(prime[i]) mu[j] = mu[j]*-1;
            if(prime[i]) prime[j] = false;
            V[j].push_back(i);
        }
    }
}

ll bigMod(ll a, ll r)
{
    if(r == 0) return 1;
    if(r == 1) return a%MOD;
    ll ret = bigMod(a, r/2);
    ret = (ret*ret)%MOD;
    if(r & 1) ret = (ret*a)%MOD;
    return ret;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    sieve();
    ll n, k;
    scanf("%lld %lld", &n, &k);
    for(ll i=0; i<=k; i++){
        power[i] = bigMod(i, n);
    }
    memset(f, 0, sizeof f);
    ll tot = 0, curAns = 0;
    for(ll i=2; i<=k; i++){
        for(ll j=0; j<V[i].size(); j++){
            ll div = V[i][j];
            ll toAdd = power[i/div]-f[div];
            toAdd = (toAdd+MOD)%MOD;
            f[div] = power[i/div];
            toAdd = toAdd*mu[div];
            toAdd = (toAdd+MOD)%MOD;
            curAns += toAdd;
        }
        f[i] = 1;
        curAns += f[i]*mu[i];
        ll cur = power[i]+curAns;
        cur = (cur+MOD)%MOD;
        cur = cur^i;
        cur = cur%MOD;
        tot += cur;
    }
    tot = tot%MOD;
    cout << tot;
}