LOJ6053 简单的函数
题目大意 给定积性函数 $f(p^c) = p \oplus c$。对 $1000000007$ 取模求前缀和。 分析 Min25 板子题。 const ll mod = 1000000007, inv2 = 500000004; const int maxn = 200001; ll n, prime[maxn], cnt, w[maxn], s[maxn], c[maxn]; ll sqrt_n, m; ll mo(ll x) { return (x + mod) % mod; } ll f_p(ll p, ll e) { return p ^ e; } int id(ll x) { return x <= sqrt_n ? x : m - (n / x) + 1; } ll F(long long n, int k) { if (n <= prime[k]) return 0; ll ret = s[id(n)] - s[prime[k]]; for (int i = k + 1; i <= cnt && prime[i] * prime[i] <= n; i++) { ll pi = prime[i], pk = pi; for (int c = 1; pk * pi <= n; c++, pk *= pi) ret += f_p(pi, c) * F(n / pk, i) + f_p(pi, c + 1); } return mo(ret); } int main() { n = rr(); sqrt_n = sqrt(n + 0....