Ấn Nút

Xem PDF

Điểm: 400 (p) Thời gian: 1.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nhân ngày quốc tế thiếu nhi, ami đã tặng em gái của Flow God xấu-trai-hơn-ami một chiếc máy thần kì. Trên chiếc máy là 2 nút màu tím và hồng, cùng 2 số \(H\)\(I\). Nếu ấn nút màu tím, số \(H\) sẽ tăng 1 đơn vị, nếu ấn nút màu hồng, số \(I\) sẽ tăng 1 đơn vị. Flow God ghen tuông vì ami đã tặng cho em gái cưng của mình một món quà cool ngầu như thế, bèn tìm ra cách để ami phải mất mặt.

Flow God xấu-trai-hơn-ami muốn ami ấn các nút tím và hồng tổng cộng không quá F lần. Sau khi thực hiện các thao tác, giả sử 2 số mà ami nhận được là \(N\)\(R\), Flow God muốn \(gcd(N,R)\) là lớn nhất có thể. Nhắc lại, \(gcd(a,b)\) là một số \(c\) lớn nhất mà cả \(a\)\(b\) đều chia hết cho \(c\) (quy ước \(gcd(0, n)=gcd(n, 0)=n\) với mọi số nguyên dương \(n\)). Tuy nhiên, ami quá thần thánh, đã tìm ra kết quả siêu nhanh. Flow God tức tối, giận cuom1999 chém ma. "ma" ở đây chính là các bạn tham gia contest.

Các bạn cần trả lời \(q\) câu hỏi của Flow God, mỗi câu hỏi có dạng \(H\) \(I\) \(F\). Cần in ra \(gcd(N,R)\) lớn nhất, \(N\)\(R\) là các số nhận được, sau khi ấn hai nút tím và hồng không quá \(F\) lần.

Input

  • Dòng đầu tiên chứa một số nguyên dương \(q\) là số câu hỏi của Flow God xấu-trai-hơn-ami.
  • Tiếp theo là \(q\) dòng, mỗi dòng chứa một bộ số nguyên không âm \(H\) \(I\) \(F\) là một câu hỏi.

Output

  • In ra \(q\) dòng, mỗi dòng là một số nguyên là \(gcd(N,R)\) lớn nhất có thể đạt được.

Dữ liệu đảm bảo luôn có kết quả.

Constraints

  • \(H, I \leq 10^5\)
  • \(q \leq 10^2\)
  • \(F \leq 10^{13}\)

Scoring

  • Subtask \(1\) (\(5\%\) số điểm): \(H = 0, I \leq 10^5, F \leq 10^{13}, q \leq 10^2\).
  • Subtask \(2\) (\(20\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F \leq 10^{5}\).
  • Subtask \(3\) (\(10\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F = 0\)
  • Subtask \(4\) (\(65\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F \leq 10^{13}\)

Example

Test 1

Input
3
0 1 1
1 1 2
2 4 1
Output
2
2
2
Note

Với \(0\) \(1\), có thể ấn nút hồng \(1\) lần để thành \(0\) \(2\). \(Gcd(0,2)\) = \(2\). Có thể chứng minh đây là kết quả lớn nhất.
Với \(1\) \(1\), có thể ấn nút hồng \(1\) lần, nút tím \(1\) lần để thành \(2\) \(2\). \(Gcd(2,2)\) = \(2\). Có thể chứng minh đây là kết quả lớn nhất.
Với \(2\) \(4\), có thể không ấn nút nào. \(Gcd(2,4)\) = \(2\). Có thể chứng minh đây là kết quả lớn nhất.


Bình luận


  • 2
    NguyenHuuNhatQuang    9:07 p.m. 4 Tháng 6, 2020

    Em xin đóng góp lời giải cho bài này:

    Gọi tổng \(k\)\(h+i+f\).

    Ta cho 1 biến \(t\) chạy từ 1 đến \(sqrt(k)\)

    -- Hàm xử lý biến t (trả về gcd tối ưu) --

    Trường hợp 1: \(t=gcd(n,r)\) thì ta kiểm tra xem có thỏa đề không (số lượng số thêm vào nhỏ hơn \(f\)).

    Trường hợp 2: \(t=(n+r)/gcd(n,r)\) để gcd(h,n) lớn nhất ta chọn \(h+n\) là số lớn nhất có thể và chia hết cho \(t\). Sau đó ta kiểm tra như trên.

    Trả về giá trị gcd(n,r) lớn nhất trong 2 trường hợp trên.
    Nếu không có giá trị nào thỏa thì trả về -1.

    -- Quay lại bài toán --

    Giả sử tìm được \(gcd\) thỏa rồi (hàm trả về 1 só khác -1).

    Nếu số \(gcd\) đó lớn hơn \(sqrt(m)\) thì bài toán được hoàn thành.

    Nếu số đó nhỏ hơn \(sqrt(m)\) thì chạy tiếp đến khi tìm được.

    ----//----


    • 1
      SPyofgame    5:22 a.m. 30 Tháng 6, 2020

      Lời giải của bạn đã được đưa vào phần hướng dẫn UwU