1090 - Trailing Zeroes (II)

Number theory এর খুব সুন্দর একটি সমস্যা । আগ্রহীরা আগে নিজে চেষ্টা করে দেখতে পার ।

Problem Statement:
       Find the number of trailing zeroes for the following function: mCn * p^q

Solution :

     ১। যেহেতু mCn = m!/(n!)/(m-n) ! কাজেই প্রথমে m!  ,n! এবং (m-n)! এ কতটি ২ আছে তা বের কর    
      ২ ।  মনে কর তাদের মধ্যে ২ আছে যথাক্রমে a2,b2,c2
      ৩। তাহলে mCn এ ২ আছে no_of_2 = a2-(b2+c2)
      ৪।  একই ভাবে  mCn এ ৫ আছে no_of_5 = a5-(b5+c5)
      ৫। নিচের Algorithm follow করে P এর মধ্যে ২ কতবার আছে তা বের কর । মনে কর P তে ২ আছে n1 বার ।

Algorithm:
     while( n>0 && !(n%2) )
    {
            n=n/n1;
            ++no;
    }

   ৬।  কাজেই mCn*p^q এ total 2 আছে  no_of_2 += n1 * q

    ৭। একই ভাবে  mCn*p^q এ total 5 আছে  no_of_5 .

   ৮।   এইবার নিচের step টি খেয়াল করে দেখ ।

Algorithm :

if(no_of_2<no_of_5)
            zero=no_of_2;
        else
            zero=no_of_5;

৯। বাহ এইতো খুব সুন্দর মতই শেষ করতে পেরেছ এই সমস্যার সমাধান ।

Code :

#include<iostream>
using namespace std;

int no_of_2,no_of_5;

int  no_of_zero_in_factorial(int  n,int n1)
{
    int  number=0;
    while(n>0)
    {
        number+=n/n1;
        n/=n1;
    }
    return number;
}

void  calculate_zero(int  m,int  n)
{
    int a2,a5,b2,b5,c2,c5;
    a2 = no_of_zero_in_factorial(m,2);
    a5 = no_of_zero_in_factorial(m,5);
    b2 = no_of_zero_in_factorial(n,2);
    b5 = no_of_zero_in_factorial(n,5);
    c2 = no_of_zero_in_factorial(m-n,2);
    c5 = no_of_zero_in_factorial(m-n,5);

    no_of_2=a2-(b2+c2);
    no_of_5=a5-(b5+c5);

}

int prime_factorize(int n,int n1)
{
    int no=0;
    while( n>0 && !(n%n1) )
    {
            n=n/n1;
            ++no;
    }
    return no;
}

int  main()
{
     int  i,test,n,m,p,q,zero;
    cin>>test;
    for(i=1;i<=test;i++)
    {
        cin>>m>>n>>p>>q;

        calculate_zero(m,n);

        no_of_2+=prime_factorize(p,2)*q;
        no_of_5+=prime_factorize(p,5)*q;

        if(no_of_2<no_of_5)
            zero=no_of_2;
        else
            zero=no_of_5;
        cout<<"Case "<<i<<": ";
        cout<<zero<<endl;

        no_of_2 = 0;
        no_of_5 = 0;
    }
    return 0;
}

সবশেষে তোমার জন্য রইল অনেক শুভকামনা । ভাল থেক সব-সময় ।