Blog

Problem link

আলোচনাঃ
আমাকে ( nCr * p^q ) এর শেষে কয়টা 0 আছে তা বের করা লাগবে। n,r,p,q এর মান খুব ছোট হলে খুব সহজেই হিসাব করা যেত। কিন্তু n, r, p, q এর highest value হতে পারে 10^6 পর্যন্ত। তাই আমাদের এমন কোনো observation বের করা লাগবে যা দিয়ে খুব সহজেই solve করা যায়।

উত্তরঃ
যেহেতু আমাদের ( nCr * p^q ) এর শেষে কয়টা 0 আছে তা বের করা লাগবে আর আমরা জানি,শুধুমাত্র N! এর শেষে কয়টা 0 আছে তা বের করতে হলে সেই সংখ্যাতে কয়টা 5 আছে তা বের করলেই হয়। না জানলে এই লেখাটা পড়তে পারো। কিন্তু অন্য ক্ষেত্রে 2 and 5 দুইটাই count করা লাগে। মানে কোনো number এর prime factorization থেকে যদি বলতে হয় সেখানে শেষে কয়টা 0 আছে তাহলে আমাদের উত্তর হবে 2^x ও 5^y এর minimum. মানে min(x,y) বের করা লাগবে। N! এ always 5 এর সংখ্যা, 2 থেকে কম হবে কারণ N!=123…n । কিন্তু prime factorization হচ্ছে ঐ number কে prime number দিয়ে represent করা।যেমনঃ 100= 2^2 * 5^2 . তাই এখানে 5 এর সংখ্যা, 2 থেকে always কম হবে না। বেশি বা কম হতে পারে আবার সমানও হতে পারে।

তো আমরা জানি, nCr = n!/(r!*(n-r)!). সুতরাং nCr * p^q = ( n!/(r!*(n-r)!) ) * p^q . তাহলে মনে আসতে পারে n! , r! and (n-r)! এ কয়টা 5
আছে তা আলাদাভাবে বের করব এবং p^q তে min(2,5) বের করে গুণ দিলেই হবে। কিন্তু এটা করলে হবে না। কারণ আগেই বলেছি N! হচ্ছে 123…n অন্যদিকে কোনো number এর prime factorization হচ্ছে ঐ number কে prime number দিয়ে represent করা। দুইটা সম্পূর্ণ আলাদা জিনিস। তাই nCr ও p^q দুটোতেই 2 and 5 এর সংখ্যা বের করা লাগবে। একটা উদাহরণ দেখা যাক,

5C3 * (100)^2 , where n=5, r=3, p=100, q=2

( n!/ (r!*(n-r)!) ) * p^q

= (5!/(3!*(5-3)!) ) * (2^2 * 5^2 )^2 ———–(1)

5!= 1*2*3*4*5
= 1*2*3*2*2*5

3!= 1*2*3

2!= 1*2

(1) এ মান বসিয়ে,
( (1*2*3*2*2*5)/(1*2*3)(1*2) ) * (2^2 * 5^2 )^2

যেহেতু শুধু 2 আর 5 কয়টা আছে সেটা জানলেই হবে তাই বাকি digit গুলোকে বাদ দিয়ে দিতে পারি। তাহলে হবে-

= ( (2*2*2*5)/(2)*(2) ) * (2^2 * 5^2 )^2
= ( (2^3*5^1)/(2^1)*(2^1) ) * (2^2 * 5^2 )^2
So, n!= (2^3*5^1)

r!= (2^1) = (2^1*5^0) [as,there is no 5, so we can write 5^0=1]
(n-r)!= (2^1) = (2^1*5^0) [as,there is no 5, so we can write 5^0=1]

power গুলোকে m,n,o,p,q,r,x,y দিয়ে replace করে দিলে দাড়ায়,

( n!/(r!*(n-r)!) ) * p^q
=> ( (2^m * 5^n)/(2^o * 5^p)(2^q * 5^r) ) * (2^x * 5^y )^2
=> ( (2^(m-o-q+2x)) * (5^(n-p-r+2y)) —————(2) [ আমরা জানি, গুণ আকারে থাকলে power গুলো যোগ হয়, আর ভাগ আকারে থাকলে power গুলো বিয়োগ হয় ]

তার মানে, m,o,q,2x হচ্ছে 2 এর count অন্যদিকে n,p,r,2y হচ্ছে 5 এর count.

বিঃদ্রঃ যদি শুধুমাত্র p^q বের করা লাগে তাহলে p এর শেষে কতগুলো 0 আছে তা বের করে q এর সাথে গুণ দিলেই হবে। যেমনঃ (100)^2 . এখানে p এর শেষে 2টা 0 আছে। তাহলে উত্তর হবে 2*q = 2*2 = 4 .

C++ Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
vector<int> an,ar,anr;

int findTwoFive(int n,int x){
    int cnt=0;
    while(n>0){
        cnt+=(n/x);
        n/=x;
    }
    return cnt;
}

int findTwoFive2(int n,int x){
    int cnt=0;
    while(n%x==0){ // prime factorization of 100 = 2^2 * 5^2 
        cnt++;     // So, we count the power of 2 and 5
        n/=x;  
    }
    return cnt;
}

int main(){
    int t,sum,cs=1;
    scanf("%d",&t);
    while(t--){
        int n,r,q,p;
        cin>>n>>r>>p>>q;

        int twoUp=0,twoDown=0,fiveUp=0,fiveDown=0;
      // for n!
        twoUp=findTwoFive(n,2);
        fiveUp=findTwoFive(n,5);

      // for r!
        twoDown=findTwoFive(r,2);
        fiveDown=findTwoFive(r,5);

      // for (n-r)!
        twoDown+=findTwoFive(n-r,2);
        fiveDown+=findTwoFive(n-r,5);

      // for p^q     
        twoUp+=findTwoFive2(p,2)*q;
        fiveUp+=findTwoFive2(p,5)*q;

        int two=twoUp-twoDown; // From (2), first part 
        int five=fiveUp-fiveDown; // From (2), second part
        
        int ans=min(two,five); // took the minimum count between 2 and 5
        printf("Case %d: %d\n",cs,ans);
        cs++;
   
    }
}