LightOj 1045 - Digits of Factorial Solution

Problem:

$T$ সংখ্যক টেস্ট কেস আছে, যেখানে $T\leq 50000$

প্রতি কেসে দুইটা সংখ্যা দেয়া আছে, $n$ ও $b$, যেখানে, $1\leq n\leq 10^6, \quad 1\leq b\leq 10^3$

বলতে হবে, b based number system এ $n!$ (Factorial of n ) এ কতগুলো ডিজিট থাকবে ।

Problem link: LightOj 1045

 Soultion:

আমরা জানি, 10 based number system এ $x$ এর ডিজিট সংখ্যা = $\lfloor log_{10} x \rfloor + 1$

একইভাবে, $b$ based number system এ $x$ এর ডিজিট সংখ্যা = $\lfloor log_{b} x \rfloor + 1$

লগারিদমের সূত্রানুসারে,

\[log_x y = log_x z \times log_z y \]

\[\implies log_z y = \frac {log_x y}{log_x z}\]

\[\therefore log_b n = \frac {log_{10} n}{log_{10} b}\]

আবার, আমরা জানি,

\[log_{10} {(x \times y \times z)} = log_{10} {x} + log_{10} {y} + log_{10} {z}\]

যেহেতু, $n! = 1 * 2 * 3 * 4 * .......... * n$ , অতএব, 

\[log_{10} {(n!)} = log_{10} {1} + log_{10} {2} + .......... + log_{10} {n}\]

অতএব, আমরা আগেই $10^6$ পর্যন্ত সব সংখ্যার $log$ এর মান বের করে অ্যারেতে রাখব ।

এরপরে, প্রতি কেসে শুধু $n$ ও $b$ এর মান ইনপুট নেব এবং $\lfloor \frac {log_{10} n}{log_{10} b} \rfloor + 1$ এর মান প্রিন্ট করে আউটপুটে দেখাব ।

Code: