Hướng dẫn cho Summer Contest #02 - Sổ tay cũ
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: ,
Ý tưởng
\[
1, 3, 7, 13, 21, 31, 56, 89, 130, 179, 267, 301, 374, 543, 640, 857, 1313, 2419, 4115, 6581, \dots
\]
Dãy này có quy luật là:
\[
n^2 + a
\]
Trong đó:
- \(n\) là số chính phương hoặc số nguyên tố theo thứ tự từ \(0\).
- \(a\) là số thứ tự của \(n\) trong dãy (bắt đầu từ \(1\)).
Ví dụ:
| Thứ tự | \(n\) | \((n^2+a)\bmod10\) |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 3 |
| 3 | 2 | 7 |
| 4 | 3 | 3 |
| 5 | 4 | 1 |
| 6 | 5 | 1 |
| 7 | 7 | 6 |
Ta thu được đúng các phần tử đầu tiên của dãy.
Gọi:
\[
cnt(M)
\]
là số lượng số nguyên tố hoặc số chính phương không vượt quá \(M\).
Khi đó:
\[
cnt(M)=\pi(M)+\lfloor\sqrt M\rfloor+1
\]
trong đó:
- \(\pi(M)\) là số lượng số nguyên tố không vượt quá \(M\).
- \(\lfloor\sqrt M\rfloor+1\) là số lượng số chính phương:
\[
0^2,1^2,\dots,\lfloor\sqrt M\rfloor^2.
\]
Để tìm phần tử thứ \(k\), ta nhị phân trên giá trị.
Nếu:
\[
cnt(M)\ge k
\]
thì phần tử thứ \(k\) không lớn hơn \(M\).
Ngược lại nếu:
\[
cnt(M)<k
\]
thì phần tử thứ \(k\) lớn hơn \(M\).
Do đó ta tìm giá trị nhỏ nhất \(M\) sao cho:
\[
cnt(M)\ge k.
\]
Khi đó chính là số thứ \(k\) cần tìm.
Code AC(C++)
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N_MAX;
ll S;
vector<ll> g_large;
vector<ll> g_normal;
void init_lucy(ll n) {
N_MAX = n;
S = sqrt(n);
g_large.assign(S + 1, 0);
g_normal.assign(S + 1, 0);
for (ll i = 1; i <= S; i++) {
g_large[i] = (n / i) - 1;
g_normal[i] = i - 1;
}
for (ll p = 2; p <= S; p++) {
if (g_normal[p] == g_normal[p - 1]) continue;
ll num_primes = g_normal[p - 1];
ll p2 = p * p;
ll max_i = min(S, n / p2);
for (ll i = 1; i <= max_i; i++) {
ll target = n / (i * p);
ll current_g = (target <= S) ? g_normal[target] : g_large[i * p];
g_large[i] -= (current_g - num_primes);
}
for (ll i = S; i >= p2; i--) {
g_normal[i] -= (g_normal[i / p] - num_primes);
}
}
}
ll get_prime_count(ll M) {
if (M < 2) return 0;
if (M <= S) return g_normal[M];
ll i = N_MAX / M;
if (i <= S) return g_large[i];
return g_normal[S];
}
ll count_elements(ll M) {
if (M < 0) return 0;
ll primes = get_prime_count(M);
ll squares = (ll)(sqrt(M)) + 1;
return primes + squares;
}
ll get_n_at_pos(ll k) {
ll low = 0, high = N_MAX;
ll ans = 0;
while (low <= high) {
ll mid = low + (high - low) / 2;
if (count_elements(mid) >= k) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}
int get_final_digit(ll k) {
ll n = get_n_at_pos(k);
ll n_mod = n % 10;
ll k_mod = k % 10;
return (n_mod * n_mod + k_mod) % 10;
}
int main() {
freopen("oldbook.inp", "r", stdin);
freopen("oldbook.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll x, y;
if (cin >> x >> y) {
ll max_k = max(x, y);
ll required_n = 0;
if (max_k <= 10) {
required_n = 30;
} else {
double ln_k = log((double)max_k);
required_n = (ll)(max_k * (ln_k + 2.0));
}
init_lucy(required_n);
cout << get_final_digit(x) << " " << get_final_digit(y) << "\n";
}
return 0;
}
Bình luận