本文章没有找到对应的语言版本

题目传送门

SP22268 ETFS - 欧拉函数筛法 题解

题目大意

给定区间 $[a, b]$，求区间内每个数的欧拉函数值 $\varphi(n)$。

算法思路

很显然，$10^{12}$ 的数据是不可能线性做的，但是 $b - a \leq 10^6$，那么我们就可以只求出区间内的 $\varphi(i)$。

那么就要用到这个玩意：

欧拉函数公式：

令

$$ n = p_1^{k_1} \times p_2^{k_2} \times \dots \times p_m^{k_m} $$

则：

$$ \varphi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right) = n \prod_{p|n} \frac{p-1}{p}\\ $$

看不懂一点

那么就可以这么做：

  1. 预处理素数（求出所有小于等于 $\sqrt{b}$ 的素数）

    • 大于 $\sqrt{b}$ 的素数在区间中最多出现一次（除了它本身）。
    • 所以只需筛到 $\sqrt{b}$ 就可以处理所有可能的质因子了。

  2. 区间筛质因子：

    • 对每个预处理出的素数 $p_i$，找到区间内所有 $p_i$ 的倍数。
    • 记录每个数的质因子 $p_i$，同时将原数不断除以 $p_i$ 直到不能整除。

  3. 计算欧拉函数：

    • 对区间内的每个数，利用记录的质因子和公式计算 $\varphi(n)$。
    • 如果筛完后剩余部分大于 $1$，说明它是一个大于 $\sqrt{b}$ 的质因子，也需要计算。

然后就没有了。

Code

为你献上！

#include <bits/stdc++.h>
#define ll long long
#define str string
#define db double
using namespace std;

constexpr ll MAXN = 1e6 + 10;
ll l, r, vl[MAXN]; // vl[i]: 区间中第i个数，会不断除以质因子
bitset<MAXN + 10> vis;
vector<ll> primes, vec[MAXN]; // vec[i]: 区间中第i个数的质因子列表

// 线性筛：求出所有不超过mx的素数
inline void prime(ll mx) {
	for (ll i = 2; i <= mx; ++i) {
		if (!vis[i])
			primes.emplace_back(i);
		for (auto p : primes) {
			if (i * p > mx)
				break;
			vis[i * p] = true;
			if (i % p == 0)
				break;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> l >> r;
	prime(sqrt(r) + 5);

	// 初始化：vl[i] = 区间中第i个数（从l开始）
	for (ll i = 1ll; i <= r - l + 1ll; ++i)
		vl[i] = l + i - 1ll;

	// 用素数筛区间内的数，记录质因子
	for (const ll& p : primes) {
		ll start = (l + p - 1ll) / p; // ceil(l/p)
		ll end = r / p;				  // floor(r/p)

		for (ll i = start; i <= end; ++i) {
			vec[i * p - l + 1ll /*在区间中的位置*/].emplace_back(p); // 记录质因子p

			// 去除所有p因子
			while (vl[i * p - l + 1ll] % p == 0)
				vl[i * p - l + 1ll] /= p;
		}
	}

	// 计算并输出每个数的欧拉函数值
	for (ll i = 1; i <= r - l + 1; ++i) {
		ll n = l + i - 1ll; // 原始数值
		ll phi = n;			// 初始化为n，将逐步乘(1-1/p)

		// 对每个质因子p：phi = phi / p * (p-1)
		for (const ll& p : vec[i])
			phi = phi / p * (p - 1ll);

		// 处理可能剩余的大于 sqrt(b) 的质因子
		if (vl[i] != 1ll)
			phi = phi / vl[i] * (vl[i] - 1ll);

		cout << phi << '\n';
	}

	return 0;
}

点个关注吧喵~

说些什么吧！

giscus