Elearning CodePath – CTP Online Judge

Số Đặc Biệt

SODB

🟢 Hard #Math #Combinatorics

### 📌 Thông tin chung

---
### 📝 Bài toán

Một số nguyên dương $X$ được gọi là số đặc biệt nếu thỏa mãn hai điều kiện sau:
1.  $X$ là số nguyên tố.
2.  Số lượng chữ số chẵn và số lượng chữ số lẻ trong $X$ là khác nhau.

Yêu cầu: Cho một dãy số nguyên $A = (A_1, A_2, \dots, A_N)$. Hãy đếm số lượng phần tử là số đặc biệt của dãy $A$.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `SODB.INP`:

* Dòng 1: Số nguyên dương $N$.
* Dòng 2: $N$ số nguyên dương $A_1, A_2, \dots, A_N$. Các số viết cách nhau một dấu cách.

Giới hạn:
* $1 \le N \le 2 \cdot 10^6$.
* $|A_i| \le 10^{12}$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `SODB.OUT` một số nguyên duy nhất là số lượng số đặc biệt đếm được.

---
### ✨ Ví dụ

| Input (`SODB.INP`) | Output (`SODB.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `5` <br> `121 311 122 23 241` | `2` | Dãy $A$ có hai số đặc biệt là $311$ và $241$. |

---
### 🏷 Ràng buộc

| Tỷ lệ điểm | Ràng buộc |
| :--- | :--- |
| $60\%$ | $1 \le N \le 300$; $1 \le A_i \le 50000$. |
| $20\%$ | $1 \le N \le 300$; ; abs($A_i$) ≤ $10^{12}$  |
| $20\%$ | $1 \le N \le 2 \cdot 10^6$; abs($A_i$)$ \le 2 \cdot 10^6$. |

---

✅ Đã AC: 0 / 39 submissions

📘 Lời giải

# SỐ ĐẶC BIỆT

## Subtask 1: $1 \le N \le 300$; $1 \le A_i \le 50000$

### 💡 Ý Tưởng:
Duyệt qua từng số trong dãy, kiểm tra xem nó có phải là số nguyên tố và có thỏa mãn điều kiện chữ số chẵn/lẻ hay không.

### ⏱ Độ Phức Tạp:
* **Thời gian:** $O(N \times \sqrt{M})$, với $N$ là số lượng số trong dãy và $M$ là giá trị lớn nhất trong dãy.
* **Không gian:** $O(1)$.

### 💻 Code:

```cpp
1 #include <iostream>
2 #include <vector>
3 #include <cmath>
4 using namespace std;
5
6 // Hàm kiểm tra số nguyên tố
7 bool isPrime(int n) {
8     if (n <= 1) return false; // Số <= 1 không phải nguyên tố
9     for (int i = 2; i <= sqrt(n); ++i) { // Thử chia từ 2 đến căn bậc 2 của n
10        if (n % i == 0) return false; // Nếu chia hết thì không phải nguyên tố
11    }
12    return true; // Là nguyên tố nếu không có ước nào
13 }
14
15 // Hàm kiểm tra số đặc biệt
16 bool isSpecial(int n) {
17    if (!isPrime(n)) return false; // Nếu không phải nguyên tố thì không đặc biệt
18    int evenCount = 0, oddCount = 0; // Đếm số chữ số chẵn và lẻ
19    while (n > 0) { // Duyệt qua từng chữ số
20        int digit = n % 10;
21        if (digit % 2 == 0) evenCount++; // Tăng đếm nếu chẵn
22        else oddCount++; // Tăng đếm nếu lẻ
23        n /= 10;
24    }
25    return evenCount != oddCount; // Đặc biệt nếu số chẵn và lẻ khác nhau
26 }
27
28 int main() {
29    int n;
30    cin >> n;
31    vector<int> a(n); // Mảng lưu dãy số
32    for (int i = 0; i < n; ++i) {
33        cin >> a[i]; // Đọc các phần tử của dãy
34    }
35    int count = 0; // Đếm số đặc biệt
36    for (int i = 0; i < n; ++i) {
37        if (isSpecial(a[i])) count++; // Tăng đếm nếu số đặc biệt
38    }
39    cout << count << endl;
40    return 0;
41 }
```
---

## Subtask 2: $|A_i| \le 10^{12}$

### Phân tích chi tiết:

Với giới hạn $|A_i| \le 10^{12}$, việc kiểm tra nguyên tố bằng phương pháp **trial division** (duyệt ước số) sẽ không khả thi do độ phức tạp $O(\sqrt{N})$ quá lớn. Ta cần sử dụng **Thuật toán Miller-Rabin**—một phương pháp xác suất kiểm tra nguyên tố với độ chính xác cao và thời gian chạy $O(k \cdot \log^3 n)$.

### 💡 Ý Tưởng:

* **Kiểm tra nguyên tố với Miller-Rabin:**
    * Phân tích $n-1 = d \times 2^s$.
    * Kiểm tra các điều kiện $a^d \equiv 1 \pmod{n}$ hoặc $a^{d \cdot 2^r} \equiv -1 \pmod{n}$ với $0 \le r < s$.
    * Sử dụng bộ cơ sở **deterministic** $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37$ đủ để kiểm tra chính xác cho số $< 2^{64}$.

* **Đếm chữ số chẵn/lẻ:**
    * Chuyển số thành giá trị tuyệt đối ($|A_i|$).
    * Duyệt từng chữ số và phân loại chẵn/lẻ.

### 💻 Code:

```cpp
1 #include <iostream>
2 #include <vector>
3 #include <cmath>
4 using namespace std;
5 typedef long long ll;
6
7 // Tính (a^b) % mod một cách hiệu quả
8 ll modularPow(ll a, ll b, ll mod) {
9     if (b == 0) return 1;
10    ll res = modularPow(a, b / 2, mod);
11    res = (res * res) % mod;
12    if (b % 2) res = (res * a) % mod;
13    return res;
14 }
15
16 // Kiểm tra cơ sở a có thỏa mãn điều kiện Miller-Rabin không
17 bool witnessTest(ll a, ll n, ll d, int s) {
18    ll x = modularPow(a, d, n);
19    if (x == 1 || x == n - 1) return true;
20    for (int r = 1; r < s; r++) {
21        x = (x * x) % n;
22        if (x == n - 1) return true;
23    }
24    return false;
25 }
26
27 // Kiểm tra nguyên tố với Miller-Rabin
28 bool isPrime(ll n) {
29    if (n <= 1) return false;
30    if (n <= 3) return true;
31    if (n % 2 == 0) return false;
32
33    // Phân tích n-1 = d*2^s
34    int s = 0;
35    ll d = n - 1;
36    while (d % 2 == 0) {
37        d /= 2;
38        s++;
39    }
40
41    // Bộ cơ sở deterministic cho n < 2^64
42    vector<ll> bases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
43    for (ll a : bases) {
44        if (a >= n) continue;
45        if (!witnessTest(a, n, d, s)) return false;
46    }
47    return true;
48 }
49
50 // Kiểm tra điều kiện chữ số chẵn/lẻ
51 bool checkEvenOddDigits(ll num) {
52    num = abs(num);
53    int even = 0, odd = 0;
54    while (num > 0) {
55        int digit = num % 10;
56        (digit % 2 == 0) ? even++ : odd++;
57        num /= 10;
58    }
59    return even != odd;
60 }
61
62 int main() {
63    int n;
64    cin >> n;
65    vector<ll> arr(n);
66    for (int i = 0; i < n; i++) cin >> arr[i];
67
68    int count = 0;
69    for (ll x : arr) {
70        if (x <= 1) continue;
71        if (isPrime(x) && checkEvenOddDigits(x)) count++;
72    }
73    cout << count << endl;
74    return 0;
75 }
```
---

## Subtask 3: $1 \le N \le 2 \times 10^6$; $|A_i| \le 2 \times 10^6$

### 💡 Ý Tưởng:
Kiểm tra nguyên tố bằng **Sàng Eratosthenes**.

### ⏱ Độ Phức Tạp:
* **Thời gian:** Trong bài toán này, có thể coi là $O(N \log N)$
* **Không gian:** $O(\max|A_i|)$.

### 💻 Code:

```cpp
1 #include <iostream>
2 #include <vector>
3 #include <cmath>
4 using namespace std;
5
6 int main() {
7     // Khai báo biến lưu số lượng phần tử
8     int n;
9     // Đọc N từ SODB.INP (giả lập bằng cin)
10    cin >> n;
11    vector<long long> a(n); // Mảng lưu dãy số
12    long long maxVal = 0; // Giá trị lớn nhất trong dãy
13    for (int i = 0; i < n; ++i) {
14        cin >> a[i]; // Đọc các phần tử
15        maxVal = max(maxVal, abs(a[i])); // Tìm giá trị tuyệt đối lớn nhất
16    }
17
18    // Sàng Eratosthenes để tìm số nguyên tố 
19    vector<bool> isPrime(maxVal + 1, true);
20    isPrime[0] = isPrime[1] = false; // 0 và 1 không phải nguyên tố
21    for (int p = 2; (long long)p * p <= maxVal; ++p) {
22        if (isPrime[p]) { // Nếu p là nguyên tố
23            for (long long i = (long long)p * p; i <= maxVal; i += p) {
24                isPrime[i] = false; // Đánh dấu các bội của p không phải nguyên tố
25            }
26        }
27    }
28
29    int count = 0; // Đếm số đặc biệt
30    for (int i = 0; i < n; ++i) {
31        // Kiểm tra nguyên tố và số dương
32        if (a[i] > 1 && a[i] <= maxVal && isPrime[a[i]]) {
33            int evenCount = 0, oddCount = 0; // Đếm số chữ số chẵn và lẻ
34            long long num = abs(a[i]);
35            while (num > 0) {
36                int digit = num % 10;
37                if (digit % 2 == 0) evenCount++; // Tăng đếm nếu chẵn
38                else oddCount++; // Tăng đếm nếu lẻ
39                num /= 10;
40            }
41            if (evenCount != oddCount) count++; // Tăng đếm nếu thỏa mãn điều kiện
42        }
43    }
44    // Ghi kết quả ra SODB.OUT (giả lập bằng cout)
45    cout << count << endl;
46    return 0;
47 }