[Quảng Bình - TS10 - 2024] Bài 4: Robot

Điểm: 20,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Pascal, PyPy, Python, ~~Scratch~~

Em cùng nhóm bạn đang tham gia cuộc thi lập trình cho Robot. Nhiệm vụ lần này của robot là nhanh chóng mở được ~N~ cánh cửa bí mật để tiến vào phòng chứa kho báu. Trên mỗi cánh cửa có in một số nguyên dương ~x~ và một nút nhấn có màn hình đang hiển thị một số nguyên dương ~y~; mỗi lần nhấn nút thì số ~y~ hiển thị trên màn hình sẽ tăng lên ~1~. Cánh cửa sẽ mở khóa nếu ước chung của ~x~ và ~y~ lớn hơn ~1~.

Yêu cầu: Em hãy lập trình cho robot tìm ra số lần nhấn nút ít nhất để mở từng cánh cửa, nhanh chóng tiến vào phòng chứa kho báu.

INPUT

Dòng ~1~: Gồm số nguyên dương ~N~ là số lượng cánh cửa (~1 \le N \le 100~).
Dòng thứ ~i~ trong ~N~ dòng tiếp theo: Mỗi dòng chứa hai số nguyên ~x~ và ~y~ cách nhau một dấu cách (~2 \le x, y \le 10^9~).

OUTPUT

Với mỗi cặp số ~x~ và ~y~ trong dữ liệu vào, ghi ra một số nguyên là số lần nhấn nút ít nhất tương ứng. Mỗi số ghi trên một dòng riêng biệt.

SAMPLE INPUT

SAMPLE OUTPUT

0
2
1

SUBTASKS

~30 \%~ số test ứng với ~30 \%~ số điểm có ~N = 1~, ~2 \le x, y \le 10^5~.
~30 \%~ số test ứng với ~30 \%~ số điểm có ~N \le 100~, ~2 \le x, y \le 10^5~.
~40 \%~ số test ứng với ~40 \%~ số điểm có ~N \le 100~, ~2 \le x, y \le 10^9~.

Bình luận

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

phucan858 đã bình luận lúc 25, Tháng 11, 2025, 6:19

3 bạn huy chương vàng IOI 2029 cùng góp sức làm bài này, đây là lời giải:

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
using ll = long long;
void AC() {
    ll x,y; cin >> x >> y;
    ll ans = LLONG_MAX;
    for(ll i =2; i * i <= x; i++) {
        if(x % i == 0) {
            if(y % i != 0) ans = min(ans, i-(y%i));
            else ans = 0;
            while(x % i == 0)x/=i;
        }
    }
    if(x > 1) {
        ll now;
        if(y % x == 0) now = 0;
        else now = x - (y % x);
        ans = min(ans, now);
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q; cin >> q;
    while(q--) AC();
    return 0;
}