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:

	#include<bits/stdc++.h>
	using namespace std;
	double logg[1000005];
	int main()
	{
	int t, n, b;
	cum[0] = 0;
	for(int i=1;i<=1000000;i++)
	logg[i]=logg[i-1] + logg(i);
	scanf("%d", &t);
	for(int cas=1;cas<=t;cas++)
	{
	scanf("%d %d", &n, &b);
	long long cnt=logg[n]/log(b) + 1;
	printf("Case %d: %lld\n", cas, cnt);
	}
	return 0;
	}

view raw LightOj 1045 - Digits of Factorial.cpp hosted with ❤ by GitHub