Editorial for Bedao Mini Contest 07 - LOGA


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.

Author: bedao

Cách tiếp cận "ngây thơ"

Ta thấy trong C++ có ~2~ hàm tính Loga cơ bản là log2 cho phép tính ~log_2(x)~ và log cho phép tính ~log_{10}(x)~ và ta có sẵn một công thức: ~log_b(a) = \frac{log_c(a)}{log_c(b)}~ ~(*)~ với ~c~ là một hệ số bất kỳ.

Ở đây C++ cho ta ~2~ hệ số Loga cơ bản ( như đã đề cập ở trước ) là ~2~ và ~10~, ta có thể lấy bất kỳ một trong hai số để áp vào công thức ~(*)~, từ đó ta hoàn toàn có thể tính ~log_a(b^x)~ rồi phân tích kết quả của phép này ra thừa số nguyên tố, nhưng do ~b~ có thể lên tới ~10^{18}~ và ~x~ là ~10^6~ nên có thể bị tràn số khi thực hiện phép ~b^x~.

Cách tiếp cận tối ưu

Để hiểu về lý thuyết chung của phép Loga trong toán, bạn đọc có thể tìm hiểu tại đây.

Ta biết rằng toán học có những phép tính cơ bản nhất là dạng cộng, trừ, nhân và chia. Nhưng để hiểu kĩ hơn về phép tính Loga này thì ta cần phải nắm vững được các phép tính cơ bản, từ đó ta có một số ý nghĩa của phép chia như sau:

  1. Phép chia cho biết số lần cần cộng từ số ~A~ để được số ~B~.
  2. Phép nhân là cộng nhiều lần thì phép chia là trừ nhiều lần.

Từ cách nhìn đó, ta có thể hiểu tương tự đối với ý nghĩa của phép Loga:

  1. Phép Loga cho biết số lần cần nhân từ số ~A~ để được số ~B~.
  2. Phép mũ là nhân nhiều lần thì phép Loga là chia nhiều lần.

Nhận xét 1: Ta có dữ kiện từ để bài: ~a~ là một sô nguyên tố và ~a \leq b~, ta xem ~a~ là số chia và ~b~ là số bị chia, từ đó ta có ~2~ trường hợp:

  • ~b~ là bội của ~a^y~ ( ~b~ chia hết cho ~a^y~ ) với ~y~ là số nguyên ~( y \geq 1 )~: việc của ta bây giờ chỉ là đếm số lần xuất hiện của ~a~ trong ~b~, tức là số lần ~b~ chia cho ~a~ để được ~1~, số lần xuất hiện này chính là ~y~, đáp án của ta cho phép ~log_a(b)~ là ~y~, khi phân tích ~y~ ra dạng thừa số nguyên tố, ta có ~y = P_1^{W_1} \times P_2^{W_2} \times \dots \times P_l^{W_l}~~(**)~ với: ~P~ là thừa số nguyên tố của ~y~, ~W~ là số mũ của thừa số nguyên tố ~P~, ~l~ là số lượng thừa số nguyên tố của ~y~.
  • ~b~ không là bội của ~a^y~ ( ~b~ không chia hết cho ~a^y~ ) với ~y~ là số nguyên ~(y \geq 1)~: rõ ràng số lần xuất hiện của ~a~ trong ~b~ giờ đây sẽ là số thực, ở dạng số thực sẽ không thể biểu diễn dưới dạng thừa số nguyên tố được, nên khi xảy ra trường hợp này ta sẽ in ~-1~.

Nhận xét 2: Nếu như ~log_a(b)~ là đếm số lần xuất hiện của ~a~ trong ~b~, vậy ~log_a(b^x)~ là số lần xuất hiện của ~a~ trong ~b~ được gấp lên ~x~ lần, do đó công thức của đề bài sẽ biến đổi từ ~log_a(b^x)~ về ~x \times log_a(b)~, mà ~log_a(b)~ đã được tính từ ~(**)~, vậy nhiệm vụ còn lại của ta chỉ là phân tích số ~x~ ra dạng thừa số nguyên tố mà thôi, khi phân tích ~x~ ra dạng thừa số nguyên tố, ta có ~x = p_1^{w_1} \times p_2^{w_2} \times \dots \times p_k^{w_k}~ ~(***)~ với: ~p~ là thừa số nguyên tố của ~x~, ~w~ là mũ của thừa số nguyên tố ~p~, ~k~ là số lượng số thừa số nguyên tố của ~x~.

Từ ~(**)~ và ~(***)~, đáp án của bài toán là: ~p_1^{w_1} \times p_2^{w_2} \times \dots \times p_k^{w_k} \times P_1^{W_1} \times P_2^{W_2} \times \dots \times P_l^{W_l}~


Comments

Please read the guidelines before commenting.



  • 1
    codernhi  commented on 17, Nov, 2021, 16:03

    không biết mình có hiểu sai hay không nhưng tại sao loga(b) = a^y vậy nhỉ? Mình tưởng phải là loga(b)=y chứ nhỉ vì y là tần suất xuất hiện a trong số lượng thừa số của b. Ví dụ log2(8)=3 mà 2^3=8. Mong admin hoặc các bạn giải đáp hộ mình, mình xin cảm ơn ạ.


    • 0
      LeThanhMinh  commented on 18, Nov, 2021, 10:11

      cảm ơn bạn nhé team đã sửa lại <3