传送门

---

题目大意

给定积性函数$f(p^k)=p\oplus c$，求${\sum }_{i=1}^{n}f(i)$

解题思路

这个题目满足$f(p)=p-1,p>2$，且$f(p^k)$能够快速求出，而且数据范围也是线性筛解决不了的，杜教筛也无法构造，那么只能考虑亚线性筛，那么就是$min\_25$筛了

$min\_25$筛传送门

对于$2$的特殊情况，我们可以仍然先按照$f(2)=2-1$来计算，然后在计算过程中每次遇到$2$就将答案加上2即可，在$S(n,j)$函数中，显然当$j=1$时代表第一个质数，也就是$2$筛过之后的和，那么这时将答案加$2$，其余部分均和模板类似

//
// Created by Happig on 2020/10/4
//
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define ENDL "\n"
#define lowbit(x) (x&(-x))
#define mkp(x, y) make_pair(x,y)
#define mem(a, x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 1e6 + 10;
ll inv2 = 5e8 + 4;ll prime[maxn], sum[maxn];
ll w[maxn], id1[maxn], id2[maxn], g[maxn], g1[maxn];
bitset<maxn> vis;
ll n;
int m, cnt, tot;inline ll getID(ll x) {return x <= m ? id1[x] : id2[n / x];
}inline void getMod(ll &x) {x %= Mod;x = x < 0 ? x + Mod : x;
}void init() {vis.reset();vis[1] = 1;m = sqrt(n + 0.5), cnt = tot = 0;for (int i = 2; i <= m; i++) {if (!vis[i]) {prime[++cnt] = i;sum[cnt] = sum[cnt - 1] + i;}for (int j = 1; j <= cnt && 1LL * i * prime[j] <= m; j++) {vis[i * prime[j]] = 1;if (i % prime[j] == 0) break;}}for (ll l = 1, r; l <= n; l = r + 1) {r = n / (n / l);w[++tot] = n / l;g[tot] = (w[tot] - 1 + Mod) % Mod;g1[tot] = w[tot] % Mod * (w[tot] + 1) % Mod * inv2 % Mod;g1[tot]--;if (n / l <= m) id1[n / l] = tot;else id2[r] = tot;}for (int i = 1; i <= cnt; i++) {for (int j = 1; j <= tot && prime[i] * prime[i] <= w[j]; j++) {ll k = getID(w[j] / prime[i]);g[j] -= g[k] - i + 1;g1[j] -= prime[i] * (g1[k] - sum[i - 1] + Mod) % Mod;getMod(g[j]);getMod(g1[j]);}}
}ll S(ll x, int y) {if (x <= 1 || prime[y] > x) return 0;ll k = getID(x);ll ans = (g1[k] - sum[y - 1] - g[k] + y - 1 + (y == 1 ? 2 : 0) + Mod) % Mod;for (int i = y; i <= cnt && prime[i] * prime[i] <= x; i++) {ll pe = prime[i];for (int e = 1; pe * prime[i] <= x; e++, pe *= prime[i]) {ans = (ans + (prime[i] ^ e) * S(x / pe, i + 1) % Mod + (prime[i] ^ e + 1) % Mod) % Mod;}}return ans % Mod;
}int main() {//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;init();ll ans = S(n, 1) + 1;getMod(ans);cout << ans << ENDL;return 0;
}