Hướng dẫn cho LQDOJ CUP 2022 - Final Round - LUCKY
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:
Subtask \(1\) (\(20\%\) số điểm): \(N = 2\) và \(D \leq 10^3\).
Tutorial
Vì \(N = 2\) và \(D\) đủ nhỏ nên ta có thể duyệt \(X\) và \(Y\) từ \(1\) đến \(D\) và kiểm tra xem \(\gcd(X, Y)\) có thuộc đoạn \([A, B]\) và \(\text{lcm}(X, Y)\) có thuộc đoạn \([C, D]\) không.
Độ phức tạp: \(\mathcal{O}(D^2)\).
Solution
#include <bits/stdc++.h>
using namespace std;
long long N, A, B, C, D;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("LUCKY.inp", "r", stdin);
freopen("LUCKY.out", "w", stdout);
cin >> N >> A >> B >> C >> D;
int ansưer = 0;
for (int X = 1; X <= D; X++) {
for (int Y = 1; Y <= D; Y++) {
int gcd = __gcd(X, Y);
int lcm = X * Y / gcd;
ansưer += (A <= gcd && gcd <= B && C <= lcm && lcm <= D);
}
}
cout << ansưer << "\n";
return 0;
}
Subtask \(2\) (\(30\%\) số điểm): \(N = 2\).
Tutorial
Đặt \(g = \gcd(X, Y)\) và \(l = \text{lcm}(x, y)\), ta có \(X = x \cdot g\) và \(Y = y \cdot g\) (\(\gcd(x, y) = 1\)).
Ta có: \(l \cdot g = X \cdot Y = x \cdot y \cdot g^2 \Leftrightarrow \displaystyle \frac{l}{g} = x \cdot y\).
Vì \(\displaystyle D \leq A \cdot 10^7 \Leftrightarrow \left\lfloor \frac{D}{A} \right\rfloor \leq 10^7\) nên ta có thể duyệt từng giá trị \(k\) từ \(1\) đến \(\displaystyle \left\lfloor \frac{D}{A} \right\rfloor\) và đếm số lượng cặp \(l, g\) sao cho \(\displaystyle \frac{l}{g} = k\) và \(x \cdot y = k\).
-
Vì \(A \leq g \leq B\) và \(\displaystyle C \leq l \leq D \Leftrightarrow C \leq g \cdot k \leq D \Leftrightarrow \left\lceil \frac{C}{k} \right\rceil \leq g \leq \left\lfloor \frac{D}{k} \right\rfloor\) nên ta có \(\displaystyle \max\left( A, \left\lceil \frac{C}{k} \right\rceil \right) \leq g \leq \min \left( B, \left\lfloor \frac{D}{k} \right\rfloor \right)\). Vậy số lượng cặp \(l, g\) thỏa mãn là \(\displaystyle \min \left( B, \left\lfloor \frac{D}{k} \right\rfloor \right) - \max\left( A, \left\lceil \frac{C}{k} \right\rceil \right) + 1\).
-
Vì \(\gcd(x, y) = 1\) tức là \(x\) và \(y\) không có thừa số nguyên tố chung. Gọi \(s\) là số lượng thừa số nguyên tố phân biệt của \(k\). Vậy số lượng cặp \(x, y\) thỏa mãn là \(2^s\).
Đáp án là tổng của tích giữa số lượng cặp \(l, g\) thỏa mãn và số lượng cặp \(x, y\) thỏa mãn với mỗi \(k\).
Độ phức tạp: \(\mathcal{O}(???)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e7 + 5;
const int MOD = 1e9 + 7;
long long N, A, B, C, D;
int pw2[30];
int prime[MAX_N];
void eratosthenes() {
memset(prime, -1, sizeof(prime));
for (int i = 2; i < MAX_N; i++) {
if (prime[i] == -1) {
for (int j = i; j < MAX_N; j += i) {
prime[j] = i;
}
}
}
}
int countPrimeDivisor(int x) {
int result = 0;
while (x > 1) {
int pr = prime[x];
result++;
while (x % pr == 0) {
x /= pr;
}
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("LUCKY.inp", "r", stdin);
freopen("LUCKY.out", "w", stdout);
eratosthenes();
cin >> N >> A >> B >> C >> D;
pw2[0] = 1;
for (int i = 1; i < 30; i++) {
pw2[i] = pw2[i - 1] * 2 % MOD;
}
int answer = 0;
for (int k = 1; k <= D / A; k++) {
long long left = max((C + k - 1) / k, A), right = min(D / k, B);
long long num = max(0LL, right - left + 1) % MOD;
answer = (answer + pw2[countPrimeDivisor(k)] * num) % MOD;
}
cout << answer << "\n";
return 0;
}
Subtask \(3\) (\(30\%\) số điểm): \(D \leq A \cdot 10^5\).
Tutorial
Trước tiên, ta cần giải quyết được một bài toán con sau đây: Đếm số lượng dãy gồm \(N\) phần tử có ước chung lớn nhất bằng \(1\) và bội chung nhỏ nhất bằng \(k\).
Gọi \(p_1, p_2, \ldots, p_s\) là các ước nguyên tố phân biệt của \(k\). Gọi \(P_i\) là tập hợp dãy mà mọi phần tử đều chia hết cho \(p_i\) và \(Q_i\) là tập hợp dãy mà mọi phần tử đều là ước của \(\displaystyle \frac{k}{p_i}\). Vậy đáp án là \(|X| - |P_1 \cup P_2 \cup \ldots \cup P_s \cup Q_1 \cup Q_2 \cup \ldots \cup Q_s|\) trong đó \(X\) là tập hợp dãy mà mọi phần tử đều là ước của \(k\).
Để tính được \(|P_1 \cup P_2 \cup \ldots \cup P_s \cup Q_1 \cup Q_2 \cup \ldots \cup Q_s|\), ta sẽ dùng nguyên lý bù trừ.
Đáp án là tổng của tích giữa số lượng cặp \(l, g\) thỏa mãn (ở subtask 2) và số lượng dãy gồm \(N\) phần tử có ước chung lớn nhất bằng \(1\) và bội chung nhỏ nhất bằng \(k\).
Độ phức tạp: \(\mathcal{O}(???)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e7 + 5;
const int MOD = 1e9 + 7;
long long N, A, B, C, D;
int prime[MAX_N];
int numDivisor[MAX_N];
int pw[450];
void eratosthenes() {
for (int i = 1; i < MAX_N; i++) {
numDivisor[i] = 1;
}
for (int i = 2; i < MAX_N; i++) {
if (prime[i]) {
continue;
}
for (int j = i; j < MAX_N; j += i) {
if (!prime[j]) {
prime[j] = i;
}
int cnt = 0;
for (int k = j; k % i == 0; k /= i) {
cnt++;
}
numDivisor[j] *= cnt + 1;
}
}
}
long long binPow(long long a, long long b) {
long long result = 1;
while (b) {
if (b & 1) {
result = result * a % MOD;
}
b >>= 1;
a = a * a % MOD;
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("LUCKY.inp", "r", stdin);
freopen("LUCKY.out", "w", stdout);
eratosthenes();
cin >> N >> A >> B >> C >> D;
for (int i = 1; i < 450; i++) {
pw[i] = binPow(i, N);
}
int answer = 0;
for (int k = 1; k <= D / A; k++) {
int p[10], s = 0;
for (int i = k; i > 1;) {
int minPrime = prime[i];
p[s++] = minPrime;
while (i % minPrime == 0) {
i /= minPrime;
}
}
int cur = 0;
for (int mask = 0; mask < (1 << (2 * s)); mask++) {
int prd = k;
for (int i = 0; i < s; i++) {
int tmp = (mask & (3 << (2 * i))) >> (2 * i);
if (tmp == 1 || tmp == 2) {
prd /= p[i];
} else if (tmp == 3) {
if (k % (p[i] * p[i]) != 0) {
prd = 0;
break;
}
prd /= p[i] * p[i];
}
}
if (prd) {
cur = (cur + (__builtin_popcount(mask) % 2 == 0 ? pw[numDivisor[prd]] : MOD - pw[numDivisor[prd]])) % MOD;
}
}
long long left = max((C + k - 1) / k, A), right = min(D / k, B);
long long num = max(0LL, right - left + 1) % MOD;
answer = (answer + cur * num) % MOD;
}
cout << answer << "\n";
return 0;
}
Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Số lượng dãy gồm \(N\) phần tử có ước chung lớn nhất bằng \(1\) và bội chung nhỏ nhất bằng \(k\) có thể tính bằng tích của những \((e_i + 1)^N - 2e_i^N + (e_i - 1)^N\) với \(k = p_1^{e_1} p_2^{e_2} \ldots p_s^{e_s}\).
Độ phức tạp: \(\mathcal{O}(???)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e7 + 5;
const int MOD = 1e9 + 7;
long long N, A, B, C, D;
int prime[MAX_N];
int pw[25];
long long binPow(long long a, long long b) {
long long result = 1;
while (b) {
if (b & 1) {
result = result * a % MOD;
}
b >>= 1;
a = a * a % MOD;
}
return result;
}
void eratosthenes() {
for (int i = 2; i < MAX_N; i++) {
if (prime[i]) {
continue;
}
for (int j = i; j < MAX_N; j += i) {
if (!prime[j]) {
prime[j] = i;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("LUCKY.inp", "r", stdin);
freopen("LUCKY.out", "w", stdout);
eratosthenes();
cin >> N >> A >> B >> C >> D;
for (int i = 1; i < 25; i++) {
pw[i] = binPow(i, N);
}
int answer = 0;
for (int k = 1; k <= D / A; k++) {
int cur = 1;
for (int i = k; i > 1;) {
int pr = prime[i];
int cnt = 0;
while (i % pr == 0) {
i /= pr;
cnt++;
}
cur = cur * (long long)((pw[cnt + 1] - 2 * pw[cnt] + pw[cnt - 1]) % MOD + MOD) % MOD;
}
long long left = max((C + k - 1) / k, A), right = min(D / k, B);
long long num = max(0LL, right - left + 1) % MOD;
answer = (answer + cur * num) % MOD;
}
cout << answer << "\n";
return 0;
}
Bình luận