trang chủ / đề bài / gcdspell / lời giải

Phep Tinh GCD

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả: huunguyenhuunguyen

Lời giải: Phép Tính GCD

Hướng tiếp cận

Sử dụng thuật toán Euclid để tính ước chung lớn nhất (GCD) của hai số.

Nhận xét quan trọng

  1. Thuật toán Euclid: gcd(A,B)=gcd(B,AmodB), với điều kiện dừng khi B=0, lúc đó gcd(A,0)=A.
  2. Độ phức tạp: Thuật toán Euclid chạy trong O(log(min(A,B))) bước, rất nhanh ngay cả với A,B lên đến 1018.
  3. Kiểu dữ liệu: Cần sử dụng long long (C++) hoặc kiểu số nguyên mặc định của Python (hỗ trợ số lớn) để tránh tràn số.

Thuật toán

  1. Đọc hai số A và B.
  2. Lặp: Trong khi B≠0, thay (A,B) bằng (B,AmodB).
  3. Khi B=0, giá trị của A chính là gcd(A,B) ban đầu.
  4. In kết quả.

Ví dụ: gcd(12,8)→gcd(8,4)→gcd(4,0)=4.

Độ phức tạp

  • Thời gian: O(log(min(A,B)))
  • Bộ nhớ: O(1)

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0