题目
题目描述
华华刚刚帮月月完成了作业。为了展示自己的学习水平之高超，华华还给月月出了一道类似的题：
\(Ans=\oplus_{i=1}^N(i^N\mod(10^9+7))\)
\(\oplus\) 符号表示异或和，详见样例解释。
虽然月月写了个程序暴力的算出了答案，但是为了确保自己的答案没有错，希望你写个程序帮她验证一下。
输入描述
输入一个正整数N。
输出描述
输出答案Ans。
示例1
输入
3
输出
18
说明
N=3时，\(1^3=1\) ，\(2^3=8\) ，\(3^3=27\) ，异或和为18。
示例2
输入
2005117
输出
863466972
备注
\(1\le N\le 1.3\times10^7\)
题解
知识点：筛法。
设 \(f(i) = i^N\) ，那么对于任意两个数 \(i,j\) 有 \(f(ij) = f(i) \cdot f(j)\) ，因此 \(f\) 是完全积性函数，可以用线性筛线性求出。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1.3e7 + 7;
const int P = 1e9 + 7;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
bool vis[N];
vector<int> prime;
int f[N];
int get_prime(int n) {
f[1] = 1;
int ans = 1;
for (int i = 2;i <= n;i++) {
if (!vis[i]) {
prime.push_back(i);
f[i] = qpow(i, n);
}
for (auto j : prime) {
if (i * j > n)break;
vis[i * j] = 1;
f[i * j] = 1LL * f[j] * f[i] % P;//完全积性函数
if (!(i % j)) break;
}
ans ^= f[i];
}
return ans;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
cout << get_prime(n) << '\n';
return 0;
}