Bài C: Đếm Số Nguyên Tố Modulo

Cho số nguyên tố p và số nguyên m, hãy đếm số lượng giá trị g ≤ m thỏa mãn g^(p-1) ≡ 1 (mod p).

Với số nguyên tố p, định lý Fermat nhỏ khẳng định mọi số nguyên không chia hết cho p đều thỏa mãn điều kiện này. Do đó, kết quả cần tìm là m trừ đi số bội của p trong khoảng từ 1 đến m.

#include <iostream>
using namespace std;

int main() {
    int prime, maxVal;
    cin >> prime >> maxVal;
    cout << maxVal - (maxVal / prime) << '\n';
    return 0;
}

Bài F: Sắp Xếp Thao Tác

Một dãy độ dài m khởi tạo toàn 0. Thực hiện n thao tác, mỗi thao tác gán giá trị tại một số vị trí. Hỏi có thể sắp xếp lại thứ tự các thao tác để đạt được cùng kết quả như ban đầu?

Điều kiện cần và đủ là mỗi vị trí phải có thao tác cuối cùng tác động đến nó giữ nguyên. Xây dựng đồ thị phụ thuộc giữa các thao tác, sau đó kiểm tra sự tồn tại của thứ tự topological khác với thứ tự ban đầu.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int operations, length;
    cin >> operations >> length;

    vector<vector<int>> posOps(length + 1);
    vector<int> inDeg(operations + 1, 0);
    vector<vector<int>> adj(operations + 1);

    for (int i = 1; i <= operations; i++) {
        int k;
        cin >> k;
        while (k--) {
            int pos;
            cin >> pos;
            posOps[pos].push_back(i);
        }
    }

    for (int i = 1; i <= length; i++) {
        for (int j = 0; j + 1 < posOps[i].size(); j++) {
            int u = posOps[i][j];
            int v = posOps[i][j + 1];
            adj[u].push_back(v);
            inDeg[v]++;
        }
    }

    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i <= operations; i++) {
        if (inDeg[i] == 0) q.push(i);
    }

    vector<int> order;
    while (!q.empty()) {
        int node = q.top();
        q.pop();
        order.push_back(node);
        for (int next : adj[node]) {
            if (--inDeg[next] == 0) q.push(next);
        }
    }

    bool isOriginal = true;
    for (int i = 0; i < operations; i++) {
        if (order[i] != i + 1) {
            isOriginal = false;
            break;
        }
    }

    if (isOriginal) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
        for (int i = 0; i < operations; i++) {
            cout << order[i] << " \n"[i == operations - 1];
        }
    }
    return 0;
}

Bài G: Túi Đựng Hàng

Có n đồ vật, mỗi đồ có trọng lượng w và giá trị v. Với ngân sách W và được lấy miễn phí k đồ, tìm tổng giá trị lớn nhất có thể.

Sắp xếp đồ vật theo trọng lượng tăng dần. Sử dụng quy hoạch động cho phần đầu và tính tổng giá trị lớn nhất của phần cuối được miễn phí.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int items, budget, freeItems;
    cin >> items >> budget >> freeItems;

    vector<pair<int, int>> goods(items);
    for (int i = 0; i < items; i++) {
        cin >> goods[i].first >> goods[i].second;
    }

    sort(goods.begin(), goods.end());

    vector<int> suffixSum(items + 1, 0);
    priority_queue<int, vector<int>, greater<int>> heap;
    int total = 0;

    for (int i = items - 1; i >= 0; i--) {
        total += goods[i].second;
        heap.push(goods[i].second);
        if (heap.size() > freeItems) {
            total -= heap.top();
            heap.pop();
        }
        suffixSum[i] = total;
    }

    vector<int> dp(budget + 1, 0);
    int best = 0;

    for (int i = 0; i < items; i++) {
        for (int j = budget; j >= goods[i].first; j--) {
            dp[j] = max(dp[j], dp[j - goods[i].first] + goods[i].second);
        }
        best = max(best, dp[budget] + suffixSum[i + 1]);
    }

    cout << best << '\n';
    return 0;
}

Bài I: Bộ Đếm

Thực hiện n thao tác (reset hoặc tăng 1) với m điều kiện dạng (a, b) cho biết tại thao tác thứ a, giá trị bộ đếm là b. Kiểm tra tính khả thi của các điều kiện.

Sắp xếp điều kiện theo a tăng dần. Với mỗi cặp điều kiện liên tiếp, kiểm tra chênh lệch giá trị có phù hợp với số thao tác giữa chúng.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int ops, cond;
    cin >> ops >> cond;

    vector<pair<int, int>> constraints(cond);
    for (int i = 0; i < cond; i++) {
        cin >> constraints[i].first >> constraints[i].second;
    }

    sort(constraints.begin(), constraints.end());

    for (auto &c : constraints) {
        if (c.second > c.first) {
            cout << "No\n";
            return 0;
        }
    }

    for (int i = 0; i + 1 < cond; i++) {
        int a1 = constraints[i].first, b1 = constraints[i].second;
        int a2 = constraints[i + 1].first, b2 = constraints[i + 1].second;
        if (b2 > b1 + (a2 - a1)) {
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
    return 0;
}