Hướng dẫn cho Số thập phân thứ k
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
BÀI E
Bài này mình nghĩ không phải bài dễ nhưng nếu tinh ý các bạn vẫn có thể giải ra dễ dàng, nên được xếp là bài E.
Trước hết, hãy nhìn vào thuật toán vét cạn :
A := a mod b;
For i := 1 to k-1 do a = a * 10 mod b;
Writeln(A *10 div b);
Thuật toán vét cạn trên tương đương với biểu thức
a mod b * 10 mod b * 10 mod b *... * 10 div b = a mod b * 10^(k-1) mod b * 10 div b;
Để tính \(10^{k-1}\) mod \(b\) với số mũ lớn như thế, các bạn cần thuật toán chia để trị sau :
int bigmod(int mu , int co_so , int mod)
{
if (mu == 0) return 1;
int k = bigmod(mu / 2 , co_so , mod);
if (mu % 2 == 0) return k * k % mod;
return k * k % mod * co_so % mod;
}
Nếu bị WA, các bạn hãy chú ý số \(k\) có thể lên đến \(10^{16}\), vì vậy việc nhân 2 số \(k\) lại với nhau sẽ gây tràn số, để khắc phục chuyện này, các bạn có thể viết hàm nhân 2 số tương tự như hàm tính mũ trên :
int multiply(int a , int b , int mod)
{
if (b == 0) return 0;
int k = multiply(a , b / 2 , mod);
if (b % 2 == 0) return k * 2 % mod;
return (k * 2 % mod + a) % mod;
}
Đây là kĩ thuật cực kì thông dụng trong lập trình thi đấu.
Bình luận