Hội thi tin học trẻ năm nay, BTC sẽ dự kiến sẽ tổ chức một phần thi đặc biệt . Trên một trục đường thẳng dài, BTC đã dùng các vạch đánh dấu chia thành nhiều đoạn có độ dài bằng nhau , vạch xuất phát được đánh chỉ số là 0, các vạch tiếp theo được đánh chỉ số liên tiếp từ 1,2,3,... Các thí sinh được chia thành 2 đội thi , ban đầu cả 2 đội đều ở vạch xuất phát, BTC liên tục đưa ra các câu hỏi, với mỗi câu hỏi, đội nào trả lời đúng sẽ được bước lên phía trước một vạch. Hết giờ thi, đội nào đứng ở vạch có chỉ số cao hơn là đội thắng cuộc. Hiện tại khi kết thúc giờ thi, một đội đang đứng ở vạch có chỉ số là A, một đội đang đứng ở vạch có chỉ số là B. Phần thưởng của phần thi này cũng khá đặc biệt, đội thua cuộc sẽ bước về vạch xuất phát, mỗi bước có một độ dài đúng bằng độ dài 1 đoạn. Giả sử sau mỗi bước, đội đó sẽ ở tại vạch có chỉ số là i và BTC sẽ chỉ trao thưởng khi thỏa mãn điều kiện A chia hết cho i và B chia hết cho i . Biết rằng đội thua cuộc bước về càng nhiều bước thì tiền thưởng càng giảm dần. Bạn hãy giúp đội thua cuộc biết cần bước về bao nhiêu bước rồi dừng lại để có số tiền thưởng lớn nhất? Dữ liệu vào từ tệp văn bản MAXGIFT.INP gồm 1 dòng ghi 2 số A và B cách nhau một dấu cách ( 1<=A,B<=2000000000) Kết quả ghi ra tệp văn bản MAXGIFT.OUT gồm 1 dòng ghi số bước mà đội thua cuộc phải về để có số tiền thưởng lớn nhất vd: MAXGIFT.INP MAXGIFT.OUT MAXGIFT.INP MAXGIFT.OUT 10 5 0 9 15 6 Giai thích ý tưởng giùm mik ko cần làm file hoặc text nha
2 câu trả lời
uses math;
function ucln(x,y:int64):int64;
var tmp : int64;
begin
while y > 0 do
begin tmp := x mod y;
x := y;
y := tmp;
end;
exit(x);
end;
var a,b:int64;
begin
readln(a,b);
writeln(min(a,b)-ucln(a,b));
readln
end.
*Hint? :))
Vì điều kiện là A `\vdots` i và B `\vdots` i nên số i cần tìm phải thuộc UC(A,B);
mà càng bước về nhiều thì tiền thưởng càng giảm dần
nên ta cần tìm 1 số i là lớn nhất có thể :)
`=>` i = UCLN(A,B);
mà đề yêu cầu là số bước đội thua phải bước về nên kết quả cần tìm là:
min(A,B) - UCLN(A,B);
*Code:
uses crt,math;
var i,a,b,m:longword;
begin
readln(a,b);
m:=min(a,b);
while a*b<>0 do
begin
a:=a mod b;
if a <> 0 then
b:=b mod a;
end;
writeln(m-(a+b));
readln;
end.
Câu hỏi trong lớp
Xem thêm
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết giúp các em luyện tập và củng cố kiến thức hiệu quả
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 5 Địa 8 có lời giải chi tiết
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 4 Địa 8 có lời giải chi tiết
