专栏文章

P5325 【模板】Min_25 筛

llovely_nst
P5325题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minj59zb
此快照首次捕获于
2025/12/02 03:16
3 个月前
此快照最后确认于
2025/12/02 03:16
3 个月前
查看原文

P5325 【模板】Min_25 筛（PN 筛）

定义 Powerful Number\tt{Powerful\ Number} 为每个质因子项次数至少为 22 的数。
显然的一点，任意一个 Powerful Number\tt{Powerful\ Number} 可以被表示为 a2b3a^2b^3。而在 nn 以内的 Powerful Number\tt{Powerful\ Number} 的数量即为：
∑a2b3≤n1=∑a=1n⌊na2⌋3≈∫1nn3x3dx≈(3n6−3)n3=O(n)\sum_{a^2b^3\le n} 1\\ =\sum_{a=1}^{\sqrt n}\sqrt[3]{\lfloor\frac n{a^2}\rfloor}\\ \approx \int_1^{\sqrt{n}} \frac {\sqrt[3]{n}}{\sqrt[3]{x}} \text{d} x\\ \approx (3\sqrt[6]{n}-3)\sqrt[3]n\\ =O(\sqrt{n})
这是一个重要的结论，即在 nn 以内的 Powerful Number\tt{Powerful\ Number} 的数量是 n\sqrt n 级别的。
回到本题，要求积性函数 f(pk)=pk(pk−1)f(p^k)=p^k(p^k-1)（pp 为质数）的前缀和。
设 g(x)=φ(x)xg(x)=\varphi(x)x。因为 pp 为质数，因此有 φ(p)=p−1\varphi(p)=p-1，同时便满足 f(p)=g(p)f(p)=g(p)。
设 f=g∗hf=g*h（狄利克雷卷积），则：
f(x)=∑d∣xg(d)h(xd)f(p)=g(1)h(p)+g(p)h(1)∵f(p)=g(p),g(1)=h(1)=1,∴f(p)=h(p)+f(p),h(p)=0.f(x)=\sum_{d|x} g(d)h(\frac xd)\\ f(p)=g(1)h(p)+g(p)h(1)\\ \because f(p)=g(p),g(1)=h(1)=1,\\ \therefore f(p)=h(p)+f(p),h(p)=0.
同时由上也可以得出 hh 为积性函数。因此只有当 xx 为 Powerful Number\tt{Powerful\ Number} 时才可能满足 h(x)≠0h(x)\ne0。继续推式子：
f(pk)=(g∗h)(pk)=∑d∣pkg(d)h(pkd)=∑i=0kg(pi)h(pk−i)g(pi)=φ(pi)pi=(pi−pi−1)pi=(p−1)p2i−1g(1)=1pk(pk−1)=h(pk)+∑i=1k(p−1)p2i−1h(pn−i)pk(pk−1)=h(pk)+∑i=0k−1(p−1)p2k−2i−1h(pi)h(pk)=pk(pk−1)−∑i=0k−1(p−1)p2k−2i−1h(pi)f(p^k)=(g*h)(p^k)\\ =\sum_{d|p^k} g(d)h(\frac {p^k}d)\\ =\sum_{i=0}^k g(p^i)h(p^{k-i})\\ g(p^i)=\varphi(p^i)p^i=(p^i-p^{i-1})p^i=(p-1)p^{2i-1}\\ g(1)=1\\ p^k(p^k-1)=h(p^k)+\sum_{i=1}^k(p-1)p^{2i-1}h(p^{n-i})\\ p^k(p^k-1)=h(p^k)+\sum_{i=0}^{k-1}(p-1)p^{2k-2i-1}h(p^i)\\ h(p^k)=p^k(p^k-1)-\sum_{i=0}^{k-1}(p-1)p^{2k-2i-1}h(p^i)\\
于是我们得到了 h(pk)h(p^k) 的递推式，直接递推即可算出。
ff 的前缀和等于：
∑ij≤nh(i)g(j)=∑i=1nh(i)∑j=1⌊ni⌋g(j)\sum_{ij\le n}h(i)g(j)\\ =\sum_{i=1}^nh(i)\sum_{j=1}^{\lfloor\frac ni\rfloor}g(j)
后半部分可以使用杜教筛算出，而又因为 Powerful Number\tt{Powerful\ Number} 的数量在 O(n)O(\sqrt n) 级别，因此只会有 O(n)O(\sqrt n) 个 h(i)h(i) 有值，直接算即可，时间复杂度为 O(n34)O(n^{\frac34})。

AC Code

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 5;
const int mod = 1e9 + 7 , inv3 = (mod + 1) / 3;
int n , m , k;
int power (int x , int y)
{
	int ans = 1;
	while (y)
	{
		if (y & 1) ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}
int Sum1 (int n)
{
	n %= mod;
	return n * (n + 1) / 2 % mod;
}
int Sum2 (int n)
{
	n %= mod;
	return n * (n + 1) / 2 % mod * (2 * n + 1) % mod * inv3 % mod;
}
namespace PhiSum
{
	int sum[N];
	unordered_map <int , int> f;
	int S (int x)
	{
		if (x < N) return sum[x];
	    if (f.count (x)) return f[x];
	    int ans = 0 , nxt , v;
	    for (register int i = 2;i <= x;)
	    {
	        v = x / i , nxt = x / v;
	        ans = (ans + S (v) * (Sum1 (nxt) - Sum1 (i - 1))) % mod;
	        i = nxt + 1;
	    }
	    return f[x] = (Sum2 (x) - ans) % mod;
	}
	bool vis[N];
	int pri[N] , ph[N];
	void init ()
	{
		sum[1] = 1;
		for (int i = 2;i < N;i ++)
		{
			if (!vis[i])
				pri[++ m] = i , ph[i] = i - 1;
			for (int j = 1 , k;j <= m && (k = pri[j] * i) < N;j ++)
			{
				vis[k] = 1;
				if (i % pri[j] == 0)
				{
					ph[k] = ph[i] * pri[j];
					break;
				}
				ph[k] = ph[i] * ph[pri[j]];
			}
			sum[i] = sum[i - 1] + ph[i] * i;
			sum[i] %= mod;
		}
	}
}
int a[N] , h[N] , s[N];
signed main ()
{
	ios::sync_with_stdio (0);
	cin.tie (0) , cout.tie (0);
	cin >> n;
	PhiSum::init ();
	a[++ k] = 1;
	h[k] = s[0] = 1;
	
	for (int i = 1;i <= m;i ++)
	{
		int pr = PhiSum::pri[i] , Mul2 = pr * pr;
		if (Mul2 > n) break;
		__int128 Mul = Mul2;
		for (int j = 2;Mul <= n;j ++)
		{
			s[j] = Mul % mod * (Mul - 1) % mod;
			for (int l = 0;l < j;l ++)
				s[j] = (s[j] - (pr - 1) * power (pr , 2 * j - 2 * l - 1) % mod * s[l] % mod);
			s[j] %= mod;
			Mul *= pr;
		}
		int K = k;
		for (int j = 1;j <= K;j ++)
		{
			if (a[j] * pr > n) continue;
			int mul = a[j] * Mul2;
            int cc = 2;
			while (mul <= n)
			{
				a[++ k] = mul;
				h[k] = h[j] * s[cc] % mod;
				cc ++;
				mul *= pr;
			}
		}
	}
	int ans = 0;
	for (int i = 1;i <= k;i ++)
		ans = (ans + h[i] * PhiSum::S (n / a[i])) % mod;
	cout << (ans + mod) % mod;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...