LibreOJ - 6053 简单的函数（min

传送门

---

题目大意

给定积性函数$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; }