Cho một dãy số nguyên dương thu thập ngẫu nhiên từ các mức thưởng trong một giải thưởng có cấu trúc cấp số nhân. Nhiệm vụ là xác định tỷ lệ công bội lớn nhất có thể, biểu diễn dưới dạng phân số tối giản A/B.

Phân tích bài toán

Dữ liệu đầu vào là tập hợp các phần tử thuộc một cấp số nhân chưa biết công bội. Sau khi loại bỏ trùng lặp và sắp xếp tăng dần, ta có thể biểu diễn mỗi phần tử dưới dạng: X[i] = X[0] * (p/q)^k_i với p/q là công bội cơ sở, k_i là số mũ nguyên dương.

Để tìm công bội lớn nhất, ta cần tìm số mũ chung nhỏ nhất sao cho mọi k_i đều chia hết cho nó — chính là ước chung lớn nhất của tất cả các k_i. Khi đó, công bội tối ưu sẽ là (p/q)^(GCD_của_các_k).

Chiến lược giải

1. Sắp xếp và loại bỏ phần tử trùng lặp.
2. Với mỗi phần tử khác X[0], rút gọn tỷ lệ X[i]/X[0] thành phân số tối giản a/b.
3. Tách riêng tử số và mẫu số, tìm GCD của các tử số và GCD của các mẫu số bằng thuật toán trừ lặp (do làm việc với số mũ).
4. Kết quả cuối cùng là GCD_tử / GCD_mẫu.

Thuật toán trừ lặp cho số mũ

Vì đang xử lý số mũ trong phân số, thay vì dùng chia dư, ta dùng phép chia nguyên để giảm dần:

LL find_exp_gcd(LL x, LL y) {
    if (x < y) swap(x, y);
    if (y == 1) return x;
    return find_exp_gcd(y, x / y);
}

Mã nguồn minh họa

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

typedef long long LL;
const int MAX_N = 110;

int n;
LL values[MAX_N], numerators[MAX_N], denominators[MAX_N];

LL euclid_gcd(LL a, LL b) {
    return b ? euclid_gcd(b, a % b) : a;
}

LL exp_gcd(LL u, LL v) {
    if (u < v) swap(u, v);
    if (v == 1) return u;
    return exp_gcd(v, u / v);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> values[i];
    
    sort(values, values + n);
    
    int unique_count = 0;
    for (int i = 1; i < n; ++i) {
        if (values[i] != values[i - 1]) {
            LL g = euclid_gcd(values[i], values[0]);
            numerators[unique_count] = values[i] / g;
            denominators[unique_count] = values[0] / g;
            ++unique_count;
        }
    }

    if (unique_count == 0) {
        cout << "1/1" << endl;
        return 0;
    }

    LL final_num = numerators[0], final_den = denominators[0];
    for (int i = 1; i < unique_count; ++i) {
        final_num = exp_gcd(final_num, numerators[i]);
        final_den = exp_gcd(final_den, denominators[i]);
    }

    cout << final_num << "/" << final_den << endl;
    return 0;
}