LOJ6053 简单的函数

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.01);
	m = cnt = 0;
	for (ll l = 1, r; l <= n; l = r + 1) {
		w[++m] = r = n / (n / l);
		ll mr = mo(r);
		s[m] = mr * (mr + 1) % mod * inv2 % mod - 1;
		c[m] = mr - 1;
	}
	for (ll p = 2; p <= sqrt_n; p++) {
		if (c[p] != c[p - 1]) {
			prime[++cnt] = p;
			for (ll j = m; w[j] >= p * p; j--) {
				s[j] = mo(s[j] - p * mo(s[id(w[j] / p)] - s[p - 1]));
				c[j] = mo(c[j] - (c[id(w[j] / p)] - c[p - 1]));
			}
		}
	}
	for (int i = 2; i <= m; i++)
		s[i] = mo(s[i] - c[i] + 2);
	printf("%lld", F(n, 0) + 1);
}