Biến Đổi Số

Xem dạng PDF
Gửi bài giải
Điểm: 0,20 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Tác giả:
huyhasun
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho hai số nguyên dương ~n~ và ~m~. Bạn được phép thực hiện thao tác sau (không hoặc nhiều lần):

  • Chọn một số ~x~ ~(1 \le x \le m)~ bất kỳ, sau đó gán ~n \leftarrow n \times \gcd(n,x)~. Trong đó ~\gcd(n, x)~ là ước chung lớn nhất của ~n~ và ~x~.

Người dân trên hành tinh Arrakis luôn truyền tai nhau về lời tiên tri, nếu ai tìm được cách biến đổi số ~n~ thành ~m~ bằng cách thực hiện ít thao tác nhất, người đó sẽ trở thành vị cứu tinh của vương quốc, The Messiah. Người thực hiện thử thách này phải đưa ra được một dãy thao tác biến đổi số ~n~ bất kỳ thỏa mãn, hoặc phải chỉ ra rằng không tồn tại cách để biến đổi ~n~ thành ~m~ với thao tác đã cho.

Arrakis đang lâm nguy, thánh chiến sắp nổ ra, hãy thử giải quyết thử thách xem liệu bạn có phải là người được chọn!

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 100~).

Mỗi test case gồm một dòng duy nhất chứa hai số nguyên dương ~n, m~ (~1 \leq n, m \leq 10^9~).

Output

Với mỗi test case, nếu như không tồn tại cách biến đổi số ~n~ thành ~m~ sử dụng thao tác đã cho, in ra ~-1~. Ngược lại, in ra trên một dòng số nguyên ~k~ (~1 \le k \le 200~) — số bước ít nhất để biến đổi ~n~ thành ~m~, theo sau đó là ~k~ số nguyên ~x_1, x_2, \ldots, x_k~ — các số nguyên được chọn cho từng bước theo thứ tự.

Nếu có nhiều dãy thao tác có số bước ít nhất để biến đổi ~n~ thành ~m~, hãy in ra dãy thao tác bất kỳ.

Có thể chỉ ra rằng nếu có thể biến đổi từ ~n~ thành ~m~, sẽ tồn tại dãy biến đổi có không quá ~200~ thao tác.

Scoring

Tổng điểm cho bài này là ~1250~.

Sample Input 1

5
2 2
1 6
6 216
2 12
4 2

Sample Output 1

0
-1
2 6 6
-1
-1

Notes

Ở test case đầu tiên, ~n = m = 2~, do đó không thực hiện thêm thao tác nào.

Ở test case thứ hai, ~n = 1~. Ta chỉ có thể chọn được ~x = 1~, và sau đó gán ~n \gets \gcd(1, 1) = 1~. Thao tác không thể thay đổi ~n~, do đó không tồn tại dãy thao tác hợp lệ.

Ở test case thứ 3, ~n = 6~, ~m = 216~. Trùng hợp thay, ~216 = 6^3~, ta có thể lựa chọn 2 thao tác có ~x~ đều bằng ~6~. Có thể chỉ ra rằng không có dãy thao tác để biến ~n = 6~ thành ~m = 216~ với chỉ 1 thao tác.

Ở test case thứ 5, ~n = 4~, ~m = 2~. Do ~n > m~, và các thao tác không thể giảm số ~n~, nên không tồn tại dãy thao tác thỏa mãn.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -3
    sb_anhtuan  đã bình luận lúc 5, Tháng 12, 2025, 8:48

    this problem was so ez ez everyone was kid noob haha rookie chicken


  • -4
    buiankhang673  đã bình luận lúc 9, Tháng 8, 2025, 12:35

    Ấn Vào Đây


  • -3
    nguyenmanhhung18092012  đã bình luận lúc 31, Tháng 7, 2025, 3:13

    include <bits/stdc++.h>

    using namespace std;

    define ll long long

    ll gcd(ll a, ll b) { while (b) { ll r = a % b; a = b; b = r; } return a; }

    int main() { ios::syncwithstdio(0); cin.tie(0); int t; cin >> t; while (t--) { ll n, m; cin >> n >> m;

        if (m % n != 0) {
        cout << "-1\n";
        continue;
    }

    ll k = m / n;
    ll res[1000], len = 0;
    bool ok = true;

    while (k > 1) {
        ll t = gcd(n, k);
        if (t == 1) {
            ok = false;
            break;
        }
        res[len++] = t;
        n *= t;
        k /= t;
    }

    if (!ok) {
        cout << "-1\n";
    } else {
        cout << len << "\n";
        for (int i = 0; i < len; i++) cout << res[i] << " ";
        cout << "\n";
    }
}
return 0;

    }


  • -8
    hmmmmm  đã bình luận lúc 24, Tháng 6, 2025, 7:38 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.