12/12/2023 19:24:58

An đã nghĩ ra một nhiệm vụ cho bản thân để thư giãn một chút. Anh ta chọn hai số nguyên dương a

Bài 3. Thư giãn tệp chương trình: gcd .pas ngôn ngữ lập trình là Pascal
An đã nghĩ ra một nhiệm vụ cho bản thân để thư giãn một chút. Anh ta chọn hai số nguyên dương a và
b, rồi tính ước số chung lớn nhất của các số nguyên “a giai thừa” và “b giai thừa”, tức là An muốn tìm
ƯCLN(ư!,b!).
Ta biết rằng giai thừa của số nguyên dương n, kí hiệu là n!, là tích của tất cả các số nguyên dương nhỏ
hơn hoặc bằng n. Như vậy n! = 1x2x ...X (n — 1) Xn. Ví dụ: 1! = 1, 4! = 1 X 2 X 3 X 4 = 24.
Nhắc lại rằng ước số chung lớn nhất của hai số nguyên dương X và y, kí hiệu là ƯCLN(x,y), là số
nguyên dương q lớn nhất sao cho q là ước của cả X và y.
Bạn có thể giải quyết được nhiệm vụ của An không?
Dữ liệu: Vào từ tệp văn bản gcd.inp gồm một dòng chứa hai số nguyên a và b (1 < a, b < 109;
min(a, tì) < 20, ở đó min(a, b) là số nhỏ nhất trong hai số a, b).
Kết quả: Ghi ra tệp văn bản gcd .out gồm một dòng chứa một số nguyên là ước số chung lớn nhất
của các số nguyên aỉ và b!.
Ví dụ:
gcd.inp
gcd.out
4 3
6
17 15
1307674368000
16 763121621
20922789888000

Trong ví dụ đầu tiên, 4! = 1x2x3x4 = 24 và 3! = 1x2x3 = 6, vì vậy ước chung lớn nhất của
các số nguyên 24 và 6 bằng 6.
Ràng buộc:
•       Có 60% số test ứng với 60% số điểm của bài thỏa mãn: 1 < a,b < 12;
•       20% số test khác ứng với 20% số điểm của bài thỏa mãn: 1 < a, b < 20;
•       20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

1 trả lời

+ Trả lời +4đ

Hỏi gia sư

Học gia sư

Tham khảo câu trả lời từ Trợ lý ảo Lazi

Để giải quyết bài toán này, ta có thể sử dụng thuật toán Euclid để tìm ước số chung lớn nhất (GCD) của hai số.

Thuật toán Euclid:
- Nếu b = 0, kết quả là a.
- Ngược lại, ta gọi hàm đệ quy với tham số là (b, a mod b).

Ý tưởng giải quyết bài toán:
- Đầu tiên, ta tính giai thừa của a và b bằng cách sử dụng vòng lặp.
- Tiếp theo, ta sử dụng thuật toán Euclid để tìm GCD của hai số giai thừa đã tính được.
- Kết quả là GCD của hai số giai thừa.

Code mẫu:
```Pascal
program gcd;

var
a, b, i: integer;
fact_a, fact_b, gcd: int64;

function calculateFactorial(n: integer): int64;
var
i: integer;
result: int64;
begin
result := 1;
for i := 1 to n do
result := result * i;
calculateFactorial := result;
end;

function euclideanGCD(a, b: int64): int64;
begin
if b = 0 then
euclideanGCD := a
else
euclideanGCD := euclideanGCD(b, a mod b);
end;

begin
assign(input, 'gcd.inp');
assign(output, 'gcd.out');
reset(input);
rewrite(output);

readln(a, b);

fact_a := calculateFactorial(a);
fact_b := calculateFactorial(b);

gcd := euclideanGCD(fact_a, fact_b);

writeln(gcd);

close(input);
close(output);
end.
```

Độ phức tạp:
- Vòng lặp tính giai thừa của a và b có độ phức tạp O(a) và O(b) tương ứng.
- Thuật toán Euclid có độ phức tạp O(log(min(a, b))).
- Vậy tổng độ phức tạp của thuật toán là O(a + b + log(min(a, b))).

1 trả lời

Thưởng th.10.2024

Xếp hạng

program GCD;

var
a, b: integer;
factorial_a, result: int64;

// Hàm tính giai thừa của n
function Factorial(n: integer): int64;
var
i: integer;
begin
Result := 1;
for i := 2 to n do
Result := Result * i;
end;

begin
// Đọc dữ liệu từ tệp inp
assign(input, 'gcd.inp');
reset(input);
readln(a, b);
close(input);

// Tính giai thừa của a
factorial_a := Factorial(a);

// Tính ước số chung lớn nhất giữa giai thừa của a và b
result := gcd(factorial_a, b);

// Ghi kết quả ra tệp out
assign(output, 'gcd.out');
rewrite(output);
writeln(result);
close(output);
end.

Tham gia Cộng đồng Lazi trên các mạng xã hội
Fanpage:	https://www.fb.com/lazi.vn
Group:	https://www.fb.com/groups/lazi.vn
Kênh FB:	https://m.me/j/AbY8WMG2VhCvgIcB
LaziGo:	https://go.lazi.vn/join/lazigo
Discord:	https://discord.gg/4vkBe6wJuU
Youtube:	https://www.youtube.com/@lazi-vn
Tiktok:	https://www.tiktok.com/@lazi.vn

Vui	Buồn	Bình thường

An đã nghĩ ra một nhiệm vụ cho bản thân để thư giãn một chút. Anh ta chọn hai số nguyên dương a

Đăng nhập

Mở khóa để xem toàn bộ nội dung trả lời