Tóm tắt đề bài

Cho hai số nguyên dương \(N\) và \(K\). Nhiệm vụ của bạn là tìm một dãy số \(A\) gồm \(N\) phần tử sao cho:

1. Các phần tử trong dãy đôi một phân biệt (\(A_i \neq A_j\) với \(i \neq j\)).
2. Tổng của tất cả các phần tử trong dãy chia hết cho \(K\), tức là \(\left(\sum_{i=1}^N A_i\right) \equiv 0 \pmod{K}\).
3. In ra bất kỳ dãy số nào thỏa mãn hai điều kiện trên.

Phân tích

• Giới hạn: \(N, K \leq 10^4\) và số lượng bộ test \(Q \leq 100\).
• Với giới hạn này, ta không cần tìm một dãy số quá đặc biệt hay tối ưu về giá trị. Một chiến thuật đơn giản là cố định \(N-1\) phần tử đầu tiên và điều chỉnh phần tử cuối cùng sao cho tổng thỏa mãn điều kiện chia hết cho \(K\).
• Để đảm bảo các phần tử đôi một phân biệt:
  • Ta có thể chọn \(N-1\) số nguyên dương đầu tiên là \(1, 2, 3, \dots, N-1\).
  • Gọi tổng của \(N-1\) số này là \(S\).
  • Ta cần tìm số thứ \(N\) (gọi là \(X\)) sao cho \((S + X) \equiv 0 \pmod{K}\) và \(X \notin \{1, 2, \dots, N-1\}\).
  • Để đảm bảo \(X\) không trùng với các số trước đó, ta có thể bắt đầu tìm \(X\) từ giá trị \(N\) trở đi.

Hướng giải quyết

Thuật toán

1. In ra (hoặc lưu vào mảng) \(N-1\) số nguyên dương đầu tiên: \(1, 2, 3, \dots, N-1\).
2. Tính tổng của \(N-1\) số này: \(S = \frac{(N-1) \times N}{2}\).
3. Tìm số nguyên dương \(X \geq N\) nhỏ nhất sao cho \((S + X) \pmod{K} = 0\).
4. Cách tìm \(X\):
   • Ta có thể dùng một vòng lặp bắt đầu từ \(X = N\), tăng dần \(X\) cho đến khi \((S + X) \% K == 0\).
   • Hoặc dùng công thức toán học để tìm \(X\) nhanh hơn:
     • Tính thặng dư hiện tại: \(r = S \pmod{K}\).
     • Cần tìm \(X\) sao cho \(X \equiv (K - r) \pmod{K}\).
     • Giá trị \(X\) nhỏ nhất thỏa mãn \(X \geq N\) có thể được tính toán trực tiếp. Tuy nhiên, với \(N, K\) nhỏ (\(10^4\)), vòng lặp while vẫn chạy rất nhanh.

Ví dụ minh họa

Với \(N=6, K=9\):

• \(N-1 = 5\) số đầu tiên: \(1, 2, 3, 4, 5\).
• Tổng \(S = 1 + 2 + 3 + 4 + 5 = 15\).
• Tìm \(X \geq 6\) sao cho \((15 + X) \vdots 9\):
  • Thử \(X = 6: 15 + 6 = 21\) (không chia hết cho 9).
  • Thử \(X = 7: 15 + 7 = 22\) (không chia hết cho 9).
  • Thử \(X = 8: 15 + 8 = 23\) (không chia hết cho 9).
  • Thử \(X = 9: 15 + 9 = 24\) (không chia hết cho 9).
  • Thử \(X = 10: 15 + 10 = 25\) (không chia hết cho 9).
  • Thử \(X = 11: 15 + 11 = 26\) (không chia hết cho 9).
  • Thử \(X = 12: 15 + 12 = 27\) (chia hết cho 9).
• Dãy số: \(1, 2, 3, 4, 5, 12\).

Độ phức tạp

• Thời gian: \(O(N + K)\) cho mỗi bộ test. Việc in \(N-1\) phần tử mất \(O(N)\), và vòng lặp tìm \(X\) mất tối đa \(O(K)\) bước. Tổng độ phức tạp \(O(Q \times (N + K))\), hoàn toàn thỏa mãn thời gian cho phép.
• Bộ nhớ: \(O(1)\) nếu in trực tiếp hoặc \(O(N)\) nếu lưu mảng.

Code tham khảo

Giải pháp C++

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

void solve() {
    long long n, k;
    if (!(cin >> n >> k)) return;

    long long sum = 0;
    // In ra n-1 số đầu tiên từ 1 đến n-1
    for (int i = 1; i <= n - 1; i++) {
        cout << i << " ";
        sum += i;
    }

    // Tìm số thứ n bắt đầu từ n để đảm bảo không trùng với các số trước
    for (long long i = n; ; i++) {
        if ((sum + i) % k == 0) {
            cout << i << "\n";
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Giải pháp Python

import sys

def solve():
    # Đọc tất cả input một lần để tối ưu tốc độ
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    idx = 0
    t = int(input_data[idx])
    idx += 1

    results = []
    for _ in range(t):
        n = int(input_data[idx])
        k = int(input_data[idx+1])
        idx += 2

        # Tạo n-1 số đầu tiên
        current_res = [str(i) for i in range(1, n)]

        # Tính tổng S = (n-1)*n / 2
        s = n * (n - 1) // 2

        # Tìm số x >= n sao cho (s + x) % k == 0
        x = n
        while (s + x) % k != 0:
            x += 1

        current_res.append(str(x))
        results.append(" ".join(current_res))

    print("\n".join(results))

if __name__ == "__main__":
    solve()