积性函数+欧拉筛+快速幂

PS：第一次遇见这种题目直接傻眼了，不知道这是一个积性函数，这个概念也没听说过，然后去学习了相关知识，不禁被这个题目所折服，这个题目实在太巧妙了。

1.首先做这个题目肯定需要快速幂，下面给出模板

ll fastpow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

2.其次，我们需要了解欧拉筛与积性函数之间的关系，这个题目需要求前n项的异或和就需要用到积性函数的性质，加上欧拉筛就能很好的解决这个问题，并且时间复杂度很低，下面给出欧拉筛的代码
欧拉筛

int prime[MAXN];              //保存质数
int vis[MAXN];                //记录是否被筛
int euler_sieve(int n){       //欧拉筛。返回质数的个数。
    int cnt = 0;              //记录质数个数
    memset(vis,0,sizeof(vis));
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=n;i++){             //检查每个数，筛去其中的合数
        if(!vis[i]) prime[cnt++]=i;    //如果没有筛过，是质数，记录。第一个质数是2
        for(int j=0; j<cnt; j++){      //用已经得到的质数去筛后面的数
            if(i*prime[j] >n)  break;  //只筛小于等于n的数
            vis[i*prime[j]]=1;         //关键1。用x的最小质因数筛去x
            if(i%prime[j]==0)  break;  //关键2。如果不是这个数的最小质因子，结束
        }
    }
    return cnt;                        //返回小于等于n的素数的个数
}

欧拉筛求质数+最小质因子

int prime[MAXN];      //记录质数
int vis[MAXN];      //记录最小质因子
int euler_sieve(int n){     
    int cnt=0;
    memset(vis,0,sizeof(vis));
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=n;i++){               
        if(!vis[i]){ vis[i]=i; prime[cnt++]=i;}    //vis[]记录x的最小质因子
        for(int j=0; j<cnt; j++){       
            if(i*prime[j] >n)  break;       
            vis[i*prime[j]]=prime[j];              //vis[]记录x的最小质因子
            if(i%prime[j]==0)
                break;                  
        }
    }
    return cnt;
}

以上代码都是在罗永军老师博客里参考的，老师讲的十分详细并且通俗易懂，十分感谢老师，也很幸运偶然之间得到了老师博客的地址，必会常常拜读老师的大作

有了以上的基础，那么就能很好的解决这个题目，做完这个题目之后，不禁感叹，实在太巧妙了！！！

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 13e6 + 10;
const int mod = 1e9 + 7;

ll fastpow(ll a, ll b) //快速幂
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
ll prime[maxn], fac[maxn], cnt;
bool vis[maxn];

void solve(ll n)
{
    fac[1] = 1; //初始化
    for (int i = 2; i <= n; ++i)
    {
        if (!vis[i]) //如果这个数没有被访问
        {
            prime[++cnt] = i;       //记录最小质数，用来筛去后面的数
            fac[i] = fastpow(i, n); //求解当前的函数值
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; ++j)
        {
            vis[i * prime[j]] = 1;
            fac[i * prime[j]] = fac[i] * fac[prime[j]] % mod; //公式
            if (i % prime[j] == 0)                            //如果它不是这个数的最小质因子就跳过
                break;
        }
    }
}
int main()
{
    ll n, ans = 0;
    scanf("%lld", &n);
    solve(n);
    for (int i = 1; i <= n; ++i)
        ans ^= fac[i];
    printf("%lld\n", ans);
}