牛客 华华给月月出题 （积性函数+欧拉筛+快速幂）

题目描述
华华刚刚帮月月完成了作业。为了展示自己的学习水平之高超，华华还给月月出了一道类似的题：

⊕符号表示异或和，详见样例解释。
虽然月月写了个程序暴力的算出了答案，但是为了确保自己的答案没有错，希望你写个程序帮她验证一下。
输入描述:
输入一个正整数N。
输出描述:
输出答案Ans。
输入
3

输出
18

说明

示例2
输入
2005117
输出
复制
863466972
备注:

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);
}