Editorial for Số thập phân thứ k
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
Comments