Số thứ n

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
HuyVu
Dạng bài
Điểm: 400 (p) Thời gian: 3.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


  • 1
    votuantai14112011    3:28 p.m. 31 Tháng 3, 2024

    Để giải quyết bài toán này, ta có thể sử dụng phép toán LCM (Least Common Multiple - Bội số chung nhỏ nhất) và phép toán GCD (Greatest Common Divisor - Ước số chung lớn nhất).
    Đầu tiên, chúng ta tính bội số chung nhỏ nhất (LCM) của a và b bằng cách sử dụng công thức: LCM(a, b) = a * b / GCD(a, b), trong đó GCD(a, b) là ước số chung lớn nhất của a và b.
    Tiếp theo, chúng ta tính số lượng số chia hết cho a hoặc b trong đoạn từ 1 đến n bằng cách sử dụng công thức: count = n // a + n // b - n // LCM.
    Sau đó, chúng ta tính số thứ n chia hết cho a hoặc b bằng cách sử dụng công thức: result = (n // a) * a + max(0, (n // b - n // LCM)) * b. Nếu count < n, ta cộng thêm max(0, (n - count - 1)) * LCM để tìm ra số thứ n chia hết cho a hoặc b.


    • 0
      kitsune    3:46 p.m. 31 Tháng 3, 2024

      Bạn dùng AI (hay cụ thể hơn là ChatGPT) à? Nhìn cách bạn giải thích cũng như code bạn nộp thì mình nghi ngờ lắm :)). Hơn nữa lời giải cũng chưa đúng đâu nhé.


      • -1
        votuantai14112011    3:52 p.m. 31 Tháng 3, 2024

        Với đang lm bài Chia kẹo 2 sao bay qua bài này rồi
        Bn ghim mik à hơi nghi nha:))


        • -3
          votuantai14112011    3:48 p.m. 31 Tháng 3, 2024

          Mấy cái giải thích anh mik lm còn code mik tự lm với test bài này nặng quá

      1 bình luận nữa