[LOJ6053]简单的函数

题目链接

积性函数 latex f(x)满足
f(1)=1\\ f(p^c)=p\oplus c

对于质数 latex p,有 latex f(p)=p\text{ xor }1

除了 latex f(2)=3,其余 latex f(p) 均为 latex p-1

那么转化成积性函数 latex g(x)=x,h(x)=1,求出 latex g(n,|P|),h(n,|P|)

那么 latex g(n,|P|)-h(n,|P|) 就是 latex \sum\limits_{i=1}^{n}[i\in P]F(i)

特别地,遇到 latex f(2) 时,要额外加上 latex 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll Max = 233333;
const ll mod = 1000000007;
ll n, m, sn, inv2, w[Max], g[Max], h[Max];
ll cntp, p[Max], sump[Max], id1[Max], id2[Max];
bool notp[Max];
ll qpow(ll x, ll k) {
	ll re = 1;
	for (; k; k >>= 1, x = x * x % mod)
		if (k & 1) re = re * x % mod;
	return re;
}
void Add(ll &a, ll b) {
	a = (a + b) % mod;
}
void Dec(ll &a, ll b) {
	a = (a - b + mod) % mod;
}

ll S(ll x, ll y) {
	if (x < p[y] || x <= 1) return 0;
	ll id = x <= sn ? id1[x] : id2[n / x];
	ll re = ((g[id] - h[id]) - (sump[y - 1] - (y - 1))) % mod;
	if (y == 1) re += 2;
	for (ll i = y; i <= cntp && p[i] * p[i] <= x; i++) {
		ll t = p[i], t2 = p[i] * p[i];
		for (ll j = 1; t2 <= x; j++, t = t2, t2 *= p[i]) {
			Add(re, ((p[i] ^ j) * S(x / t, i + 1) % mod + (p[i] ^ (j + 1)) % mod) % mod);
		}
	}
	return re;
}

int main() {
	inv2 = qpow(2, mod - 2);
	scanf("%lld", &n), sn = sqrt(n);
	for (ll i = 2; i <= sn; i++) {
		if (!notp[i]) {
			p[++cntp] = i;
			sump[cntp] = (sump[cntp - 1] + i) % mod;
		}
		for (ll j = 1; j <= cntp && i * p[j] <= sn; j++) {
			notp[i * p[j]] = 1;
			if (i % p[j] == 0) break;
		}
	}
	for (ll i = 1, j; i <= n; i = j + 1) {
		j = n / (n / i);
		w[++m] = n / i;
		g[m] = (w[m] % mod * ((w[m] + 1) % mod) % mod * inv2 % mod + mod - 1) % mod;
		h[m] = (w[m] - 1) % mod;
		if (w[m] <= sn) id1[w[m]] = m;
		else id2[n / w[m]] = m;
	}
	for (ll i = 1; i <= cntp; i++) {
		for (ll j = 1; j <= m && p[i] * p[i] <= w[j]; j++) {
			ll d = w[j] / p[i];
			ll id = d <= sn ? id1[d] : id2[n / d];
			Dec(g[j], p[i] * (g[id] - sump[i - 1]) % mod);
			Dec(h[j], (h[id] - i + 1) % mod);
		}
	}
	printf("%lld\n", (S(n, 1) + mod + 1) % mod);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注