আলোচনাঃ
আমরা জানি,5!=120. মান 120 হবে যখন base=10(in decimal).এখানে digit আছে 3টি। কিন্তু base=11 or base=5 হলে, 5! এ কয়টি digit থাকবে? .এটাই আমদের বের করা লাগবে।
উত্তরঃ
আমদের প্রশ্নের একটা simple version হচ্ছে , 1000 এ কয়টি digit আছে?
এটার উত্তর=log10(1000)+1 ( in base 10). log10(1000)=3+1=4.তার মানে 1000 এ 4টি digit আছে।
তাহলে, আমরা যদি 5! এ কয়টি digit আছে তা বের করতে চাই তাহলে ,
digits = log10(5!)+1 করলেই হবে। আবার 5!=1*2*3*4*5
=>digits = log10(1*2*3*4*5)+1
=>digits = log10(1)+log10(2)+log10(3)+log10(4)+log10(5)+1
[আমরা জানি, log এ value গুণ আকারে থাকলে, যোগ আকারে লেখা যায়]
আচ্ছা! তাহলে তো সহজ-ই। একটা লুপ চালাবো ।আর C++ এ তো log10() function আছেই। just যোগ করলেই হলো। কিন্তু যোগ করলেই কি হবে?
খেয়াল করে দেখি, আমাদের built-in function এ log10() আর log2() আছে । কিন্তু আমদের যখন
log3() or log100() লাগবে তখন কি করব? কারণ প্রশ্নে base এর range দেয়া আছে [2-1000].
তাহলে কি করা যায়?
আমরা ছোট বেলায় একটা base থেকে অন্য base এ convert করার একটা formula শিখেছিলাম-
এখানে, log(a)x এর x-কে আমরা 5! এর সাথে তুলনা করতে পারি। আর base = a.
তাহলে আমদের log(10)x আগে বের করা লাগবে। তাহলে হয় log(10)5!. Here, x=5!, যা আমদের
প্রশ্নের n.আর আমরা আগেই দেখেছি ,
log10(5!)= log10(1)+log10(2)+log10(3)+log10(4)+log10(5)
কিন্তু n এর মান তো always 5 হবে না। তাহলে কি প্রতিবার n এর different মানের জন্য আমরা বার বার
log(10)n! হিসাব করবো?
না, তা করা যাবে না। তাহলে TLE খাবো। তাই আমরা যেটা করতে পারি সেটা হলো, n=0-10^6 পর্যন্ত
log(10)n! আগেই pre-calculate করে রাখতে পারি। আর এটা করতে আমাদের O(N) সময় লাগবে।
এটা করলে আমদের সুবিধা হচ্ছে যে, আমরা পরে log(a)n! or log(a)x! এর মান O(1) এ বলে দিতে পারবো।আর
ডান পাশের নিচের log(10)a তো বের করার জন্য তো C++ এর log10(a) তো আছেই।
Complexity:
1) প্রথম নিয়ম অনুসারে করলে,একটা test case এ আমদের time লাগতো = O(n)*O(1)
আর test case দেয়া আছে T টা । তাহলে T টা test case এর জন্য time লাগতো = TO(n)O(1)
So, total time taken = 50000*1000000*1 = 50000000000/10^8 = 500 s
আর, given time হচ্ছে 2s.তাই TLE দিতো।
নিচে 10^8 দিয়ে ভাগ করছি কারণ CPU 1 second এ 10^8 টা operation execute করতে পারে।
(practically 10^8 থেকে বেশি কিন্তু safety এর জন্য 10^8 ধরা হয়)
2) কিন্তু pre-calculate করলে একবারই O(N) লাগবে। আর,
T টা test case চলতে লাগবে = T*O(1)
So, total time taken = ((50000*1)/10^8) + time taken for pre-calculate
= (0.0005 + x) s
আমার computer এ program টা run করতে 0.081 s লেগেছে । তাহলে pre-calculate করতে –
(0.0005+x) = 0.081
=> x = 0.081-0.0005 = 0.0795s লেগেছে।
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
#define pii pair<int,int>
#define MOD 10000007
#define PI acos(-1.0)
double lg10[N];
/**
logb(n)*loga(b)=loga(n)
logb(n)=loga(n)/loga(b)
so, logb(n!)=loga(n!)/loga(b)
so, logb(n!)=log10(n!)/log10(b)
*/
void preCal()
{
lg10[0]=0;
for(int i=1;i<=N;i++){
/// log10(n!)=log(1*2*3*..*n)
/// log10(n!)=log(1)+log(2)+log(3)+..+log(n)
///so, log(2!)=log(1)+log(2)
lg10[i]=lg10[i-1]+log10(i);
}
}
int main(){
preCal();
int t,n,base,cs=1;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&base);
/// logb(n!)=log10(n!)/log10(b)
int ans=(lg10[n]/log10(base));
printf("Case %d: %d\n",cs++,ans+1);
}
}