DIVISION - Divisiblity by 3 SPOJ Problem Solution & Logic

http://www.spoj.com/problems/DIVISION/

মোটামুটি ঝামেলার একটা প্রোবলেম , নাম্বার থিওরি সম্পরকে ভালো ধারণা না থাকলে , এটা সলভ করা সম্ভব নয়।

ধরো , N = 2 দেয়া আছে, অর্থাৎ যদি বলা হয় - ২ ডিজিট বিশিষ্ট কয়টি , বাইনারি নাম্বার আছে যেগুলো ৩ দ্বারা বিভাজ্য ।

  তাহলে ২ ডিজিট বিশিষ্ট ------    (০০)  = ০ , ৩ দ্বারা বিভাজ্য
                                                    (১১)   =  ৩ ,   ৩    দ্বারা বিভাজ্য
                                                    (১০)   = ২ , ৩ দ্বারা বিভাজ্য নয়
                                                    (০১) =  ১,  ৩ দ্বারা বিভাজ্য নয়

           তাহলে ,মোট দুইটি সংখ্যা যেমন , ০০  && ১১ শুধু   মাত্র ৩ দ্বারা বিভাজ্য ।

তাহলে , চলো দেখি ২,৩,৪,৫,৬,৭ ডিজিট বিশিষ্ট সংখ্যা'র ক্ষেত্রে কি ঘটতে পারে ?? প্যাটার্ন খোজার
চেষ্টা করি

N=1 ->1

N=2 ->2        (2*1)

N=3 ->3        (2*1)*2 - 1                        = (2^2)-1

N=4 -> 6       (2^2 -1)*2                         = ( 2 ^3 - 2 ) 

 

N=5 ->11      (2^3 – 2^1)*2 - 1              = (2^4 - 2^2 ) -1

N=6 ->22      (2^4 – 2^2 -1) *2              = (  2^5 – 2^3 -2 )

N=7 ->43      (2^5 – 2^3 – 2^1)*2 - 1    =  ( 2^6 –  2^4  –  2^2  ) - 1


 তাহলে , দেখা যাচ্ছে - যে , N এর মান যখন জোড় ,তখন এক ধরনের ধারা , এর সুত্র হবে ,
                                                     (2^N+ 2)/3

ও  N  এর  মান  যখন  বিজোড়  , তখন  এক  ধরনের  ধারা   , এর সুত্র হবে , (2^N + 1)/3

এখন দেখি ,কিছুটা  সহজ মনে হচ্ছে , তাই না   ??  কিন্তু , একটু ঝামেলা আছে -- 

যেহেতু  N এর মান অনেক বড়ো হতে পারে , তখন কিন্তু আমাদের কোড ঠিকঠাক রান 

করবে না , তাই - প্রশ্নে কিন্তু বলাই আছে যে -

 
"Print in new line the answer modulo 1000000007."

অর্থাৎ ,  আমাদের প্রিন্ট করতে হবে ।

 
( (2^N+ 2) / 3 )%1000000007 অথবা ,
( (2^N + 1 ) /3 ) %1000000007  

এখানে , আরো কিছু বিষয় আছে , Modular Multiplicative Inverse ছাড়াও আরো কিছু নিয়ম । 

এসব না জানা থাকলে , দ্রুত শিখে নেইয়া উচিত , না হলে - এই কোড'টি বুঝতে পারবে না    ।।। 

চলো কোড'টা দেখি ফেলি ------------------

#include <bits/stdc++.h>

using namespace std;

#define ULL unsigned long long

#define MOD 1000000007

#define INV 333333336 // Inverse modulo of 3 with 1000000007

ULL pow_mod(ULL n)
{
    ULL x=1,p=2;
  
    while ( n!=0 )
    {
        if(n%2!=0)
            x=(x*p)%MOD;
          
        p=(p*p)%MOD;
      
        n=n>>1;
    }
  
    return x;
}
int main()
{
    ULL n,result;
  
    while(scanf("%llu",&n)!=EOF)
      
    {
        if(n%2!=0){
            result = ((pow_mod(n)+1)*INV)%MOD;
            printf("%llu\n",result);
        }
      
        else{
              
            result = ((pow_mod(n)+2)*INV)%MOD;
            printf("%llu\n",result);
        }
    }
  
    return 0;
}