Hướng dẫn cho Viên ngọc hàm phi
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Hướng dẫn giải bài: Viên ngọc hàm phi
1. Phân tích bài toán
Bài toán yêu cầu thực hiện 2 thao tác trên mảng \(a\):
- Cập nhật đoạn \([l, r]\): Gán \(a_i = \phi(a_i)\) với mọi \(i\) trong đoạn.
- Truy vấn đoạn \([l, r]\): Tính tổng các \(a_i\) trong đoạn.
Tính chất quan trọng của hàm Phi Euler \(\phi(x)\):
- \(\phi(x)\) giảm rất nhanh. Với \(x \le 10^6\), chỉ sau tối đa khoảng 20 lần áp dụng \(\phi\), giá trị của \(x\) sẽ giảm về \(1\).
- Khi \(x = 1\), \(\phi(1) = 1\), giá trị sẽ không thay đổi nữa.
2. Subtask 1 (30% điểm): \(n, q \le 1000, a_i \le 10^3\)
Giới hạn rất nhỏ, có thể duyệt trâu từng phần tử để cập nhật và tính tổng. Ta dùng Sàng để tính trước hàm \(\phi\) cho các số tới \(10^3\). Độ phức tạp \(O(n \cdot q)\).
3. Subtask 2 (20% điểm): \(n, q \le 2 \cdot 10^5, a_i \le 2\)
Các viên ngọc ban đầu chỉ có năng lượng \(1\) hoặc \(2\).
Do \(\phi(2) = 1\) và \(\phi(1) = 1\), một viên ngọc bất kỳ nếu bị dính lời nguyền sẽ lập tức biến thành \(1\) và giữ nguyên giá trị đó mãi mãi. Bạn có thể sử dụng cấu trúc Segment Tree hoặc Disjoint Set Union (DSU) kết hợp Fenwick Tree để bỏ qua các phần tử đã bằng \(1\). Tuy nhiên, cách làm này hoàn toàn có thể gộp chung với cấu trúc của Subtask 3 bên dưới.
4. Subtask 3 (50% điểm): \(n, q \le 2 \cdot 10^5, a_i \le 10^6\)
Sử dụng Segment Tree kết hợp tối ưu:
- Mỗi node trên Segment Tree quản lý tổng của đoạn (
s) và giá trị lớn nhất của đoạn (m). - Khi có truy vấn cập nhật đoạn \([l, r]\), nếu node hiện tại có
m\(\le 1\), tức là mọi phần tử trong đoạn đều đã bằng \(1\), ta lập tức kết thúc quá trình cập nhật cho nhánh đó. - Nếu
l == r, ta gán lại giá trị lá bằng \(\phi\) của nó. - Truy vấn tính tổng diễn ra bình thường trên Segment Tree.
- Cần sàng hàm \(\phi\) tới \(10^6\) trước khi xử lý truy vấn.
Code C++ (Sub 1)
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1005];
int p[1005];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
for (int i = 1; i <= 1000; ++i) p[i] = i;
for (int i = 2; i <= 1000; ++i) {
if (p[i] == i) {
for (int j = i; j <= 1000; j += i) {
p[j] -= p[j] / i;
}
}
}
int n, q;
if (!(cin >> n >> q)) return 0;
for (int i = 1; i <= n; ++i) cin >> a[i];
while (q--) {
int t, l, r; cin >> t >> l >> r;
if (t == 1) {
for (int i = l; i <= r; ++i) a[i] = p[a[i]];
} else {
ll s = 0;
for (int i = l; i <= r; ++i) s += a[i];
cout << s << '\n';
}
}
return 0;
}
Code C++ (Sub 2 & 3 - Full AC)
C++
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int M = 1000005;
int p[M];
ll a[200005];
ll s[800005];
ll m[800005];
void build(int i, int l, int r) {
if (l == r) {
s[i] = m[i] = a[l];
return;
}
int md = (l + r) / 2;
build(i * 2, l, md);
build(i * 2 + 1, md + 1, r);
s[i] = s[i * 2] + s[i * 2 + 1];
m[i] = max(m[i * 2], m[i * 2 + 1]);
}
void upd(int i, int l, int r, int u, int v) {
if (m[i] <= 1 || l > v || r < u) return;
if (l == r) {
s[i] = p[s[i]];
m[i] = s[i];
return;
}
int md = (l + r) / 2;
upd(i * 2, l, md, u, v);
upd(i * 2 + 1, md + 1, r, u, v);
s[i] = s[i * 2] + s[i * 2 + 1];
m[i] = max(m[i * 2], m[i * 2 + 1]);
}
ll get(int i, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (u <= l && r <= v) return s[i];
int md = (l + r) / 2;
return get(i * 2, l, md, u, v) + get(i * 2 + 1, md + 1, r, u, v);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
for (int i = 1; i < M; ++i) p[i] = i;
for (int i = 2; i < M; ++i) {
if (p[i] == i) {
for (int j = i; j < M; j += i) {
p[j] -= p[j] / i;
}
}
}
int n, q;
if (!(cin >> n >> q)) return 0;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
while (q--) {
int t, l, r; cin >> t >> l >> r;
if (t == 1) upd(1, 1, n, l, r);
else cout << get(1, 1, n, l, r) << '\n';
}
return 0;
}
Code Python (Sub 2 & 3 - Full AC)
Python
import sys
sys.setrecursionlimit(300005)
def solve():
d = sys.stdin.read().split()
if not d: return
n = int(d[0])
q = int(d[1])
M = 1000005
p = list(range(M))
for i in range(2, M):
if p[i] == i:
for j in range(i, M, i):
p[j] -= p[j] // i
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(d[i + 1])
s = [0] * (4 * n + 5)
m = [0] * (4 * n + 5)
def build(i, l, r):
if l == r:
s[i] = m[i] = a[l]
return
md = (l + r) // 2
build(i * 2, l, md)
build(i * 2 + 1, md + 1, r)
s[i] = s[i * 2] + s[i * 2 + 1]
m[i] = max(m[i * 2], m[i * 2 + 1])
def upd(i, l, r, u, v):
if m[i] <= 1 or l > v or r < u: return
if l == r:
s[i] = p[s[i]]
m[i] = s[i]
return
md = (l + r) // 2
upd(i * 2, l, md, u, v)
upd(i * 2 + 1, md + 1, r, u, v)
s[i] = s[i * 2] + s[i * 2 + 1]
m[i] = max(m[i * 2], m[i * 2 + 1])
def get(i, l, r, u, v):
if l > v or r < u: return 0
if u <= l and r <= v: return s[i]
md = (l + r) // 2
return get(i * 2, l, md, u, v) + get(i * 2 + 1, md + 1, r, u, v)
build(1, 1, n)
idx = n + 2
out = []
for _ in range(q):
t = int(d[idx])
l = int(d[idx + 1])
r = int(d[idx + 2])
idx += 3
if t == 1:
upd(1, 1, n, l, r)
else:
out.append(str(get(1, 1, n, l, r)))
print('\n'.join(out))
solve()
Code Java (Sub 2 & 3 - Full AC)
Java
import java.io.*;
import java.util.*;
public class Main {
static int[] p;
static long[] a, s, m;
static void build(int i, int l, int r) {
if (l == r) {
s[i] = m[i] = a[l];
return;
}
int md = (l + r) / 2;
build(i * 2, l, md);
build(i * 2 + 1, md + 1, r);
s[i] = s[i * 2] + s[i * 2 + 1];
m[i] = Math.max(m[i * 2], m[i * 2 + 1]);
}
static void upd(int i, int l, int r, int u, int v) {
if (m[i] <= 1 || l > v || r < u) return;
if (l == r) {
s[i] = p[(int)s[i]];
m[i] = s[i];
return;
}
int md = (l + r) / 2;
upd(i * 2, l, md, u, v);
upd(i * 2 + 1, md + 1, r, u, v);
s[i] = s[i * 2] + s[i * 2 + 1];
m[i] = Math.max(m[i * 2], m[i * 2 + 1]);
}
static long get(int i, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (u <= l && r <= v) return s[i];
int md = (l + r) / 2;
return get(i * 2, l, md, u, v) + get(i * 2 + 1, md + 1, r, u, v);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
int M = 1000005;
p = new int[M];
for (int i = 1; i < M; i++) p[i] = i;
for (int i = 2; i < M; i++) {
if (p[i] == i) {
for (int j = i; j < M; j += i) {
p[j] -= p[j] / i;
}
}
}
a = new long[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
a[i] = Long.parseLong(st.nextToken());
}
s = new long[4 * n + 5];
m = new long[4 * n + 5];
build(1, 1, n);
StringBuilder out = new StringBuilder();
for (int k = 0; k < q; k++) {
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
if (t == 1) upd(1, 1, n, l, r);
else out.append(get(1, 1, n, l, r)).append("\n");
}
System.out.print(out);
}
}
Bình luận (13)