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ả:
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


  • 0
    anhphampeter    6:48 p.m. 25 Tháng 5, 2024

    include <bits/stdc++.h>

    using namespace std;
    long long g(long long n,long long a,long long b) {
    return n/b+n/a-n/(a*b/__gcd(a,b));
    }

    int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    long long t;
    cin>>t;
    for (int i=1; i<=t; i++) {
    int a,b,n;
    cin>>a>>b>>n;
    long long L =1;
    long long R=1e18;
    while (1) {
    if (L==R) break;
    if (L==R-1) {
    if (g(L,a,b)<n) L=R; break; } long long m=(L+R)/2; if (g(m,a,b)>=n) R=m;
    else L=m;
    }
    cout<<L<<'\n';
    }
    return 0;

    } than khảo code của mình đi uy tín lắm


    • 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

      • -2
        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!


        • 13
          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


          • -7
            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ở.