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.

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

There are no comments at the moment.