Olympic Sinh Viên 2023 - Chuyên tin - Ước số

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    nmk05022006  đã bình luận lúc 6, Tháng 12, 2025, 14:31 ← chỉnh sửa

    Code AC: link


  • 0
    teqi  đã bình luận lúc 29, Tháng 9, 2025, 4:41 ← chỉnh sửa

    import math def fib(n, mod): if n == 0: return (0, 1) a, b = fib(n >> 1, mod) c = (a * ((2b - a) % mod)) % mod d = (aa + b*b) % mod if n & 1: return (d, (c + d) % mod) else: return (c, d) a, b, m = map(int, input().split()) g = math.gcd(a, b) result = fib(g, m)[0] print(result)

    moi nguoi tham khao nhe cau 1


  • 18
    YougiTuber  đã bình luận lúc 1, Tháng 12, 2024, 19:56

    Spoil ⚠️

    Subtask ~1~:

    ~a, b \le 50~, dễ dàng lưu được các số ~fib~ trong giới hạn kiểu long long và tính như bình thường

    Subtask ~2~:

    Sử dụng tính chất ~\gcd(fib(a), fib(b)) = fib(gcd(a,b))~, sau đó có thể dễ dàng tính bằng nhân ma trận

    Fibonacci Numbers - cp-algorithms

    Video tính số fibonacci bằng nhân ma trận

    Nhân ma trận

    Subtask ~3~:

    Tương tự như subtask ~2~, tuy nhiên phép nhân trong lúc nhân ma trận có thể bị tràn số, cần nhân số lớn bằng chia để trị

    Nhân lấy dư - VNOI Wiki

    Video solution

    Olympic Sinh Viên 2023 - Chuyên tin - Ước số


  • -51
    Loc2008  đã bình luận lúc 27, Tháng 12, 2023, 8:27

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.