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


  • 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

      • 3 bình luận nữa