Số thứ n

Xem PDF
Tác giả:
PhanDinhKhoi
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Bạn được cho 2 số nguyên dương \(a\) và \(b\).

Viết chương trình tìm số thứ \(n\) chia hết cho \(a\) hoặc \(b\).

Input

  • Dòng đâu tiên chứa số nguyên dương \(T\) \((T \leq 10^5)\) - là số câu hỏi.
  • \(T\) dòng, mỗi dòng chứa 3 số nguyên dương \(a, b, n\) \((a,b \leq 10^4, N \leq 10^9)\).

Output

  • Gồm \(T\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

Test 1

Input 
1
2 3 10
Output 
15
Note

Giải thích Những số chia hết cho \(2\) hoặc cho \(3\) là \(2, 3, 4, 6, 8, 9, 10, 12, 14, 15, ....\)

Bình luận


  • 2
    tktungtd    7:33 p.m. 24 Tháng 5, 2022 ← chỉnh sửa 3

    tăng thời gian cho scratch đi anh, scratch xử lí chậm quá :)))

    1 phản hồi

    • -1
      huyhau6a2    8:21 p.m. 30 Tháng 11, 2021

      Mình nghĩ cái này cũng bao hàm loại trừ, nhưng có 2 số a và b thôi!


      • 14
        longkold00    11:23 a.m. 28 Tháng 10, 2021 ← chỉnh sửa 3

        Mình xin chia sẻ cách làm như sau:

        1. Ta có số số thỏa mãn chia hết cho a hoặc b <=n sẽ bằng n/a + n/b + n/LCM(a,b) . Như vậy chúng ta đã có đk để tìm kiếm số thứ n bằng chặt nhị phân đó là sử dụng 2 đầu l=1 và r= min(a,b)*n. Sau đó kiểm tra điều kiện.
        2. Các bạn có thể cải thiện thời gian bằng toán học như sau: ta sẽ tính số số thỏa mãn theo chu kì của LCM VD: như các số chia hết cho 2 or 3 sẽ có chu kì 4: (2,3,4,6), (8,9,10,12),... như vậy với n=10 thì ta chỉ cần chặn l=(10/4)LCM và r=(10/4+1)LCM

        đây là code mình đã cải thiện, các bạn có thể đọc thêm để tham khảo


        • -8
          minhtuanitk20    6:47 p.m. 4 Tháng 10, 2021

          Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.