# Bài 1 - Lịch (Callendar)
::::info
Đông là một con người (human) nên độ tuổi của đông phải có giới hạn (chắc chắn bé hơn 10^6 ngày) nên ta có thể dùng thuật brute force
::::

:::spoiler Solution
Ta lần lượt cộng thêm n ngày vào ngày ban đầu.
Mỗi lần tăng ngày lên 1:
Nếu số ngày vượt quá số ngày tối đa của tháng hiện tại thì đặt ngày về 1 và tăng tháng.
Nếu tháng vượt quá 12 thì đặt tháng về 1 và tăng năm.
Số ngày của mỗi tháng được xác định bằng mảng, riêng tháng 2 cần xét năm nhuận:
Năm nhuận nếu chia hết cho 400 hoặc chia hết cho 4 nhưng không chia hết cho 100.
Sau khi cộng đủ n ngày, in ra kết quả theo định dạng dd mm yyyy.
:::

:::spoiler Code

#include <iostream>
using namespace std;

bool isLeapYear(int year) {   //kiểm tra năm nhuận
    if (year % 400 == 0) return true;
    if (year % 100 == 0) return false;
    return year % 4 == 0;
}

int daysInMonth(int month, int year) { // tính ra ngày trong tháng hiện tại
    int days[] = {31,28,31,30,31,30,31,31,30,31,30,31};
    if (month == 2 && isLeapYear(year)) return 29;
    return days[month - 1];
}

int main() {
    int day, month, year, n;
    cin >> day >> month >> year >> n;

    while (n--) {
        day++;
        if (day > daysInMonth(month, year)) {
            day = 1;
            month++;
            if (month > 12) {
                month = 1;
                year++;
            }
        }
    }

    if (day < 10) cout << "0";
    cout << day << " ";

    if (month < 10) cout << "0";
    cout << month << " ";

    cout << year;
    return 0;
}

:::

# Bài 2 - Đỏ SM (DOSM)
::::info
:::spoiler 💡 Hint 1
Để tối ưu hóa chi phí, ta cần chọn ngày có giá pin rẻ nhất trong phạm vi $k$ ngày trước ngày ta muốn dùng pin để di chuyển
:::
::::

::::info
:::spoiler 💡 Hint 2
Ta cần dùng data stucture để lưu lại được ngày tối ưu trong phạm vi k ngày đó
:::
::::

## Subtask 1
:::: spoiler Solution ✅
Với k = 1, ta mua ngày nào thì ta chỉ có thể dùng ngày đó, do đó, ý tưởng của subtask 1 là ta cộng giá pin của từng ngày vào sau đó nhân cho 3 (do mỗi ngày cần 3 pin để chạy)
:::info
Độ phức tạp thuật toán: $\mathcal{O}(n)$
:::
::::

::: spoiler Code 💻

#include <iostream>
#include <vector>

using namespace std;

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void setup(){
    if(!fopen("DOSM.INP", "r")) return;
    freopen("DOSM.INP", "r", stdin);
    freopen("DOSM.OUT", "w", stdout);
}

int main(){
    fast();
    setup();
    
    int n,k;
    cin >> n >> k;
    long long res = 0;
    int x;
    for(int i = 1; i <= n; i++){
        cin >> x;
        res += 3LL*x;
    }
    cout << res << '\n';
    for(int i = 1; i <= n; i++) cout << 3 << ' ';
}

:::

## Subtask 2
:::: spoiler Solution ✅
Ở ngày thứ $i$, ta sẽ duyệt về trước ngày $i$ $k-1$ ngày và kiếm ngày nào có giá pin thấp nhất thì ta mua và đánh dấu vào mảng (tính cả ngày $i$)
:::info
Độ phức tạp thuật toán: $\mathcal{O}(n*k)$
:::
::::

::: spoiler Code 💻

#include <iostream>
#include <vector>

using namespace std;

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void setup(){
    if(!fopen("DOSM.INP", "r")) return;
    freopen("DOSM.INP", "r", stdin);
    freopen("DOSM.OUT", "w", stdout);
}

int main(){
    fast();
    setup();
    
    int n,k;
    cin >> n >> k;
    vector<int> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    vector<long long> cnt(n+1);
    cnt[1] = 3; // ngày 1 luôn phải mua cục pin cho ngày 1
    long long res = 3LL*a[1];
    for(int i = 2; i <= n; i++){
        int minn = a[i];
        int pos = i;
        for(int j = i-1; j > max(0,i-k); j--){
            if(minn > a[j]){
                minn = a[j];
                pos = j;
            }
        }
        res += 3LL*minn;
        cnt[pos] += 3;
    }

    cout << res << '\n';
    for(int i = 1; i <= n; i++) cout << cnt[i] << ' ';
}

:::

## Subtask 3
:::: spoiler Solution ✅
Để truy vấn những số có giá trị nhỏ nhanh, ta dùng **priority_queue** - gọi tắt là `pq`, pq này sẽ lưu 2 giá trị đó là index và giá trị tại index đó, mỗi lần lấy `pq.top()` mà index nằm ngoài phạm vi $k$ so với $i$, thì ta loại bỏ. pq sẽ đượt sort theo giá trị tại index được lưu.
:::info
Độ phức tạp thuật toán: $\mathcal{O}(n*log(n))$
:::

:::success
- Hướng tiếp cận này có thể AC cả subtask 4 nếu cài cẩn thận
- Thậm chí, trong một số trường hợp, cách này còn xử lý nhanh hơn hướng tiếp cận ở subtask 4
:::
::::

::: spoiler Code 💻

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct box{
    int idx,val;
    bool operator<(const box& other) const{ // comparator so sánh cho pq
        if(this->val == other.val){
            return this->idx < other.idx; // lưu ý rằng phải chọn ngày gần nhất
        }
        return this->val > other.val; 
    }
};

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void setup(){
    if(!fopen("DOSM.INP", "r")) return;
    freopen("DOSM.INP", "r", stdin);
    freopen("DOSM.OUT", "w", stdout);
}

int main(){
    fast();
    setup();
    
    int n,k;
    cin >> n >> k;
    vector<int> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    vector<long long> cnt(n+1);
    cnt[1] = 3; // ngày 1 luôn phải mua cục pin cho ngày 1
    long long res = 3LL*a[1];
    priority_queue<box> pq;
    pq.push({1,a[1]});

    for(int i = 2; i <= n; i++){
        while(!pq.empty() && pq.top().idx <= i - k) pq.pop(); // loại bỏ trước để giảm độ phức tạp \mathcal{O}(logn) của pq
        pq.push({i,a[i]});
        box temp = pq.top(); // lưu lại để tránh lấy pq.top() 2 lần -> giảm ĐPT
        res += 3LL*temp.val;
        cnt[temp.idx] += 3;
    }

    cout << res << '\n';
    for(int i = 1; i <= n; i++) cout << cnt[i] << ' ';
}

:::

## Subtask 4
:::: spoiler Solution ✅
Ở subtask này, để đảm bảo AC 100%, ta dùng cấu trúc dữ liệu deque kết hợp với kỹ thuật [Tìm min trên đoạn tịnh tiến](https://wiki.vnoi.info/algo/data-structures/deque-min-max)
:::info
Độ phức tạp thuật toán: $\mathcal{O}(n)$
:::
::::

::: spoiler Code 💻

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void setup(){
    if(!fopen("DOSM.INP", "r")) return;
    freopen("DOSM.INP", "r", stdin);
    freopen("DOSM.OUT", "w", stdout);
}

int main(){
    fast();
    setup();
    
    int n,k;
    cin >> n >> k;
    vector<int> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    vector<long long> cnt(n+1);
    deque<int> qu;
    long long ans = 0;

    for(int i = 1; i <= n; i++){
        if(!qu.empty() && qu.front() <= i-k) qu.pop_front();
        while(!qu.empty() && a[qu.back()] >= a[i]) qu.pop_back();
        qu.push_back(i);
        ans += a[qu.front()]*3LL;
        cnt[qu.front()] += 3;
    }

    cout << ans << '\n';
    for(int i = 1; i <= n; i++) cout << cnt[i] << ' ';
}

:::

# Bài 3: Truyện Tranh (MANGA)
:::spoiler Hint
- Đọc danh sách m tập truyện đang có
- Sắp xếp tăng dần
- Duyệt từ 1 đến n, dùng con trỏ chạy trên mảng đã sort để tìm những số bị thiếu
:::
:::spoiler Solution
-Ở mỗi testcase, sort lại danh sách cách quyển truyện trên kệ.
-Sau khi sort, dùng biến d = 1
-Với mỗi phần tử a[i]:
-Nếu a[i] > d → các số từ d đến a[i]-1 là bị thiếu
-cập nhật d = a[i] + 1
-Sau vòng lặp, nếu d ≤ n thì các số từ d đến n còn thiếu
-Độ phức tạp: O(m log m)

:::
::: spoiler Code

#include <bits/stdc++.h>
using namespace std;

int t,n,m;
int a[1000003];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1; i <= m; i++) cin >> a[i];

        sort(a+1, a+m+1);
        vector<int> missing;
        int d = 1;
        for (int i = 1; i <= m; i++) {
            while (d < a[i]) {
                missing.push_back(d);
                d++;
            }
            d = a[i] + 1;
        }
        while (d <= n) {
            missing.push_back(d);
            d++;
        }

        if (missing.empty()) {
            cout << 0 << '\n' << 0 << '\n';
        } else {
            cout << missing.size() << '\n';
            for (int x : missing) cout << x << ' ';
            cout << '\n';
        }
    }
    return 0;
}

:::
# Bài 4: Kết Giới Ma Pháp(BARRIER)

## Subtask 1 ($N, Q \le 1000$)
:::: spoiler Solution ✅
* Duyệt trâu từng truy vấn. Với mỗi truy vấn $(l, r, x)$, chạy vòng lặp từ $l$ đến $r$.
* Kiểm tra `__gcd(a[i], x) == 1` thì tăng biến đếm.
:::info
Độ phức tạp: $O(Q \cdot N \cdot \log(\max A))$
:::
::::
## Subtask 2 ($A_i, x \le 10$)
:::: spoiler Solution ✅
Do giá trị nhỏ, ta dùng mảng cộng dồn pre[v][i] là số lượng giá trị v xuất hiện trong đoạn $A[0 \dots i]$.Với mỗi truy vấn, duyệt $v$ từ 1 đến 10. Nếu $\gcd(v, x) == 1$, cộng số lượng giá trị $v$ trong đoạn $[l, r]$ vào kết quả.
:::info
Độ phức tạp: $O(N \cdot 10 + Q \cdot 10)$
:::
::::

## Subtask 3 ($x$ là số nguyên tố)
:::: spoiler Solution ✅
Khi $x$ là số nguyên tố, điều kiện $\gcd(A_i,x)>1$ nên $A_i$ chia hết cho $x$.
Bài toán trở thành: Đếm số lượng phần tử trong đoạn $[l, r]$ không chia hết cho $x$.

**Công thức:** $Ans = (r - l + 1) - Cnt(\text{vị trí } i \in [l, r] \text{ mà } A_i \; \vdots \; x)$.

Ta tiền xử lý:
1. Với mỗi giá trị $v$, `pos[v]` lưu danh sách các chỉ số $i$ mà tại đó $A_i$ chia hết cho $v$.
2. Để đếm số lượng bội số của $x$ trong đoạn $[l, r]$, ta sử dụng chặt nhị phân trên mảng `pos[x]` vừa tính được.
:::info
Độ phức tạp: $O(N\sqrt{A} + Q \log N)$
:::
::::
::: spoiler Code 💻

#include <bits/stdc++.h>
using namespace std;

#define Nexuron signed main
#define endl '\n'
#define ll long long

const int N = 2e5 + 10;
vector<int> a[N];
int Cnt (int l, int r, int x) {
    int res = upper_bound(a[x].begin(), a[x].end(), r) - lower_bound(a[x].begin(), a[x].end(), l);
    return res;
}
int n,q;
Nexuron() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    // freopen("main.INP", "r", stdin);
    // freopen("main.OUT", "w", stdout);
    cin >> n >> q;
    for (int i = 0; i < n ; i++) {
        int x; cin >> x;
        for (int j = 1; j * j <= x; j++) {
            if (x % j == 0) {
                a[j].push_back(i);
                if (j * j != x) {
                    a[x / j].push_back(i);
                }
            }
        }
    }

    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        l--; r--;
        int cnt = Cnt(l, r, x);
        int ans = (r - l + 1) - cnt;
        cout << ans << " ";
    }
    return 0;
}

:::
## Subtask 4 (Không có giới hạn gì thêm)
:::: spoiler Solution ✅
Sử dụng nguyên lý **Bao hàm - Loại trừ (Inclusion-Exclusion Principle)** để giải quyết trường hợp $x$ bất kỳ:
1. Phân tích $x$ thành các thừa số nguyên tố phân biệt $p_1, p_2, \dots, p_k$.
2. Một số $A_i$ hòa hợp với $x$ khi và chỉ khi $A_i$ không chia hết cho bất kỳ $p_j$ nào.
3. **Công thức:** $Ans = (r - l + 1) - \text{Cnt}(\text{số lượng } A_i \text{ chia hết cho ít nhất một } p_j)$.
4. Dùng Bitmask để duyệt qua tất cả các tập con của các ước nguyên tố. Với mỗi tập con, ta tính tích $d$ của chúng và thực hiện cộng/trừ số lượng bội của $d$ trong đoạn $[l, r]$.
:::info
**Độ phức tạp:** $\mathcal{O}(N\sqrt{A} + Q \cdot 2^k \log N)$
*(Với $k$ là số lượng ước nguyên tố phân biệt của $x$, $k \le 7$)*
:::
::::
::: spoiler Code 💻

#include <bits/stdc++.h>
using namespace std;

#define Nexuron signed main
#define endl '\n'
#define ll long long

const int N = 2e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int n, q;
int min_prime[N];
inline void sieve() {
    for (int i = 1; i < N; i++) min_prime[i] = i;
    for (int i = 2; i * i < N; i++) {
        if (min_prime[i] == i) {
            for (int j = i * i; j < N; j += i) {
                if (min_prime[j] == j) min_prime[j] = i;
            }
        }
    }
}
vector<int> trial_div(int x) {
    vector<int> factors;
    while (x > 1) {
        int p = min_prime[x];
        factors.push_back(p);
        while (x % p == 0) x /= p;
    }
    return factors;
}
vector<int> a[N];
int Cnt (int l, int r, int x) {
    int res = upper_bound(a[x].begin(), a[x].end(), r) - lower_bound(a[x].begin(), a[x].end(), l);
    return res;
}
Nexuron() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    // freopen("main.INP", "r", stdin);
    // freopen("main.OUT", "w", stdout);
    sieve();
    cin >> n >> q;
    for (int i = 0; i < n ; i++) {
        int x; cin >> x;
        for (int j = 1; j * j <= x; j++) {
            if (x % j == 0) {
                a[j].push_back(i);
                if (j * j != x) {
                    a[x / j].push_back(i);
                }
            }
        }
    }
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        l--; r--;
        vector<int> primes = trial_div(x);
        int m = primes.size(), cnt = 0;
        for (int msk = 1; msk < (1 << m); msk++) {
            int d = 1, bits = __builtin_popcount(msk);
            for (int i = 0; i < m; i++) {
                if ((msk >> i) & 1) d *= primes[i];
            }
            if (bits % 2 == 1) cnt += Cnt(l, r, d);
            else cnt -= Cnt(l, r, d);
        }
        int ans = (r - l + 1) - cnt;
        cout << ans << " ";
    }
    return 0;
}

:::
# Bài 5: Năng lượng X (XENERYGY)
:::spoiler Hint
Gọi: d = ước dương lớn nhất bé hơn n
Khi đó: d = n / p với p là ước nguyên tố nhỏ nhất của n
=> Qua mỗi lần Quặng X phát ra năng lượng:
n → n - (n / spf[n])

Trong đó spf[n] là ước nguyên tố nhỏ nhất của n.
:::
:::spoiler Solution
-Dùng sàng để tính spf[i] cho mọi i<=10^7
-Với mỗi testcase:Lặp cho đến khi n == 1:
1. Tính năng lượng phát ra: p = n / spf[n]
2. Đếm số lần xuất hiện của p
3. Giảm n = n - p

Trong đó spf[n] là ước nguyên tố nhỏ nhất của n.
:::
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;


const int N = 10000000;

int spf[N + 1];          // spf[i] = ước nhỏ nhất > 1 của i
vector<int> primes;

void sieve() {
    for (int i = 2; i <= N; i++) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * 1LL * p > N) break;
            spf[i * p] = p;

            if (p == spf[i]) break;
        }
    }

}

int t,n;

int main()
{
    freopen("XENERGY.INP","r",stdin);
    freopen("XENERGY.OUT","w",stdout);
    sieve();
    cin>>t;
    while(t--)
    {
        cin>>n;
        map<int,int> mp;
        while(n>1)
        {

            mp[n/spf[n]]++;
            n= n - n/spf[n];
        }
        for(auto it = mp.begin();it!=mp.end();it++)
        {
            cout<<(*it).first<<" "<<(*it).second<<' ';
        }
        cout<<'\n';
    }
}
:::