Calculate Summation of GCD(i,n); for i = 1 to n

আমাদের এবারের কাজ হল ১ থেকে n পর্যন্ত সবগুলো সংখ্যার সাথে n এর গ.সা.গু. বের করে তাদের যোগফল বের করা।
শুনতে ব্যাপারটি সহজ মনে হলেও, আসলে ঠিক সহজ না, যদি না আমরা সঠিক এপ্রোচ না জানি। নরমালি আমরা যখন প্রোগ্রামিং এ নতুন, তখন আমরা ১ থেকে n পর্যন্ত লুপ চালায়ে তাদের যোগফল বের করতাম।


এখন কথা হচ্ছে, এভাবে করলে আমরা বড় বড় সংখ্যার জন্য আমরা TLE খাবো। যেমন n = 1000000000 এর জন্য আমাদের প্রচুর সময় লাগবে, ( ইচ্ছে করলে উপরের কোডটি নিজ দায়িত্বে রান করে দেখে নিতে পারো :3 )

এখন তাহলে আমরা কিভাবে এর সমাধান করবো? খেয়াল করলে দেখবো যে, আমরা যখন ১ থেকে n পর্যন্ত স্বাভাবিক সংখ্যাগুলোর সাথে n এর গসাগু বের করার চেষ্টা করছি,তখন আসলে আমরা প্রতিবার n এর সবগুলো বিভাজক( all divisor ; there maybe multiple occurance of divisors) নিয়ে তাদের যোগফলটা নিচ্ছি। যেমনঃ  n = 8 হলে, gcd(1,8) + gcd(2,8) + gcd(3,8) + gcd(4,8) + gcd(5,8) + gcd(6,8) + gcd(7,8) + gcd(8,8)  = 1+2+1+4+1+2+1+8 = 20।
এখানে খেয়াল করে দেখি যে, আমরা কিন্তু ১,২,৪,৮ ছাড়া আর কিছু যোগ করছিনা! আর এই সংখ্যাগুলি কিন্তু আসলে ৮ এর বিভাজক (divisor)। আমরা আপাতত গোনায় বাদ রাখলাম কোন সংখ্যা কতবার নিচ্ছি, কিন্তু আসল কথা হচ্ছে আমরা n এর divosr গুলিকেই নিচ্ছি আমাদের ক্যাল্কুলেশন এর জন্য। তাহলে বুঝা যাচ্ছে আমাদের আসলে n এর divisor গুলি বের করতে হবে। আর আমরা O(√n) কমপ্লেক্সিটি তে n এর divisor বের করতে পারি। কাজেই, n = 1000000000 এর জন্য আমরা 31622.77.. কমপ্লেক্সিটিতে divisor গুলি বের করে, এরপরে আমাদের বাকি কাজ করবো।

তাহলে  n = 8 এর জন্য, আমাদের যোগফল অনেকটা এরকম হবে দেখতেঃ

\sum _{ i=1 }^{ 8 }{ gcd(i,n) } = coef1*(1)+coef2*(2)+coef3*(4)+coef4*(8)

এখানে coef1,coef2… এগুলোই আমাদের বের করতে হবে। divisor গুলি আমরা আগেই পেয়ে গেছি।
১ থেকে n পর্যন্ত সংখ্যাগুলোর সাথে n এর গ.সা.গু. বের করতে গেলে,গ.সা.গু = ১ কতবার আসবে, সেই সংখ্যাটা আসলে n এর অয়লার ফাংশন। অয়লার ফাংশন সম্পর্কে না জানলে এই লিঙ্ক দেখার অনুরোধ রইল আগে।
আচ্ছে এখান থেকে আমরা একটু মনযোগ দেয়ার চেষ্টা করি, 

phi (8) = 4.
phi (4) = 2.

phi (2) = 1.
phi (1) = 1.
আমরা এখানে আসলে ৮ এর divisor গুলির phi এর মান দেখলাম।
আচ্ছে এখন দেখা যাক, phi(8) = 4 এর জন্য, কোন কোন জোড়া নিলে আমাদের গসাগু ১ আসছেঃ
(1,8), (3,8), (5,8), (7,8); কাজেই, আমাদের coef1 = 4 হবে। ( coef1*(1); এই 1 এর মানে হচ্ছে, ঐসব জোড়া আমরা নিবো, যাদের মাঝের গ.সা.গু. = 1 হবে, এরকম জোড়া আছে 4 টি, কাজেই আমাদের coef1 = 4 )
এখন আমরা বের করবো coef2 এর মান। কাজেই আমাদের বের করতে হবে এমন কতটি জোড়া আছে, যারা 8 এর সাথে গ.সা.গু.  = 2 হবে। এজন্য আমাদের দরকার phi(8/2) = phi(4) এর মান। আমরা আগেই বের করে রেখেছি, phi(4) = 2. কাজেই আমাদের coef2 = 2. একইভাবে, coef3,coef4 বের করতে পারবো আমরা। ফাইনালি,

coef1 = phi(8/1) = phi(8) = 4. ; divide by first divisor = 1.
coef2 = phi(8/2) = phi(4) = 2. ; divide by second divisor = 2.
coef3 = phi(8/4) = phi(2) = 1. ; divide by third divisor = 4.
coef4 = phi(8/8) = phi(1) = 1. ; divide by forth divisor = 8.

কাজেই, আমাদের ফাইনাল রেজাল্ট ঃ
phi(8/1)*1 + phi(8/2)*2 + phi(8/4)*4 + phi(8/8)*8
= 4*1 + 2*2 + 1*4 + 1*8 = 20
 

অ্যালগরিদম (Algorithm)

without pre computing phi values:


এখন আমাদের অনেক কুয়েরি থাকলে আমাদের আগে থেকে phi এর মান বের করে রাখতে হবে। ঐ ব্যাপারটা তোমরা নিজেরা করে দেখো। আবার যদি আমাদের n এর মান অনেক বড় হয়ে যায় যে, আমরা O(√n) এও TLE খাচ্ছি, তাহলে আমাদের number theorem এর অন্যরকম এপ্রোচ নিতে হবে। এগুলো নিয়ে পরে আলোচনা করা যাবে। 

Advertisements

Euler’s Totient or Phi Function φ(n)

phi ফাংশন কি?

phi ফাংশন একটি arithmetic function যেটি count করে একটি সংখ্যা N এর সমান বা ছোট কতটি ধনাত্মক সংখ্যা আছে যেগুলো N এর  সহমৌলিক (relative prime). অর্থাৎ 1 থেকে শুরু করে N পর্যন্ত মোট কতটি সংখ্যা আছে যেগুলোর সাথে N এর 1 বাদে অন্য কোন সাধারন উৎপাদক (common divisor) নেই, আরেকটু সহজ করে বলতে গেলেঃ 1 থেকে N এর মাঝে, যাদের সাথে N এর GCD = 1. উদাহরন :
15 সংখ্যাটি বিবেচনা করি,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
এর মধ্যে থেকে 15 এর সাথে common divisor আছে এমন সংখ্যাগুলোকে মার্ক করিঃ
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

এই সংখ্যাগুলিকে বাদ দিবো, কেননা 15 এর গুননীয়ক ঃ 3 এবং 5. কাজেই, এদের গুনিতক (3, 5, 6, 9, 10, 12, 15) এগুলো বাদ যাবে।
তাহলে অবশিষ্ট থাকে টি সংখ্যা – 1, 2, 4, 7, 8, 11, 13, 14
সুতরাং, φ( 15 ) = 8.

এখন চিন্তা করি, মৌলিক সংখ্যার জন্য phi এর মান কত হবে?
খেয়াল করলে দেখবো যে, আসলে কোন মৌলিক সংখ্যার সাথে তার আগের সকল সংখ্যাই সহমৌলিক, অর্থাৎ এদের মাঝে ১ ছাড়া আর কোন গুননীয়ক নেই। অর্থাৎ, φ(প্রাইম) = প্রাইম – ১

7 সংখ্যাটি একটি prime number. তাহলে 7 এর জন্য,
1, 2, 3, 4, 5, 6, 7
so, φ(7) = 7-1 = 6.
so, φ(prime) = prime-1

মৌলিক সংখ্যার ক্ষেত্রে কাজটা অনেক সহজ হলেও অন্যান্য ক্ষেত্রে কিছুটা জটিল। এজন্য আমাদের একটি Theorem জানতে হবে। সেটি হলঃ

φ( i*j ) = φ( i ) * φ( j ), when i and j is relatively prime

এর জন্য, আমাদের i এবং j, উভয়কেই সহমৌলিক হতে হবে। এখন খেয়াল করি, আমরা যদি, i এবং j কে এমনভাবে নিয়ে আসতে পারি, যে তারা উভয়েই প্রাইম হবে, অর্থাৎ যেকোন সংখ্যাকে আমরা প্রাইম এর ফ্যাক্টরে নিয়ে আসতে যদি পারি, তাহলে আমাদের জন্য φ(prime) = prime-1 দিয়ে প্রতি প্রাইম ফ্যাক্টর এর phi বের করা খুবি সহজ, এবং সেখান থেকে φ( i*j ) = φ( i ) * φ( j ) এই ফর্মুলার মাধ্যমে আমরা প্রাইম ফ্যাক্টর থেকে প্রাপ্ত phi এর মান গুন করে দিলেই মূল সংখ্যার phi এর মান পেয়ে যাবো। উদাহরনঃ

φ( 30 ) = φ( 2 ) * φ( 3 ) * φ( 5 )
now, φ( 2 ) = 1, φ( 3 ) = 2, φ( 5 ) = 4.
so, φ( 30 ) = 1 * 2 * 4 = 8

অর্থাৎ 1 থেকে 30 এর মাঝে, 30 এর সাথে সহমৌলিক 8 টি সংখ্যা আছে।
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
এগুলো হলঃ 1, 7, 11, 13, 17, 19, 23, 29 (Total 8 numbers).

এখন ধরা যাক, আমরা 4-এর φ ফাংশনের মান বের করতে চাই। আমরা এখন পর্যন্ত যা জানি, তা অনুযায়ী,

 φ(4) = φ(2)*φ(2) = 1*1 = 1.

কিন্তু ,
GCD(1,4) = 1, রিলেটিভলি প্রাইম
GCD(2,4) = 2
GCD(3,4) = 1, রিলেটিভলি প্রাইম
GCD(4,4) = 4
অর্থাৎ, φ(4) = 2

এটি কিন্তু আমাদের ফর্মুলা অনুযায়ী মিলেনি। তাহলে আমরা এখান থেকে একটি জিনিস খেয়াল করতে পারি যে, যখন আমাদের প্রাইম ফ্যাক্টরের ঘাত (power) ১ হবে, কেবলমাত্র তখনি আমরা আমাদের উপোরক্ত ফর্মুলা ব্যবহার করতে পারবো। তাহলে এরকম ক্ষেত্রে আমাদের ফর্মুলার একটু পরিবর্তন আসবে এভাবে ঃ
φ( n) = n– nk-1 , when n is prime and k != 1.

তাহলে আমরা এতক্ষনের আলোচনা থেকে ৩ টি গুরুত্বপূর্ণ ব্যাপার দেখলাম। এগুলি হলঃ 

  1. φ( n ) = n – 1, when is prime and power is 1.
  2. φ( n) = n– nk-1 ,when n is prime and k != 1.
  3. φ( i*j ) = φ( i ) * φ( j ), when i and j is relatively prime.

অ্যালগরিদম (Algorithm)

আমরা 1 থেকে N পর্যন্ত লুপ চালায়ে ব্রূট ফোর্স অ্যালগরিদম লিখতে পারি এভাবেঃ

কিন্তু এটি বড় বড় সংখ্যার জন্য রান করতে অনেক সময় নিবে, কাজেই এটি তেমন ভালো এপ্রোচ না আমাদের জন্য।
এবার আমরা একটু অন্যভাবে প্রোগ্রাম করবো।

৩৬ = (২*২)*(৩*৩)
φ(৩৬) এর সর্বোচ্চ মান হতে পারে ৩৬। কাজেই আমরা ইনিশিয়ালি, result = 36 লিখে রাখবো।
এর মৌলিক গুণনীয়ক আছে দুইটিঃ ২ এবং ৩। এখন,
১ থেকে ৩৬-এর মধ্যে ২-এর গুণনীয়ক কয়টি আছে?  উত্তরঃ ৩৬/২ = ১৮ টি।
তাহলে, আমরা লিখবো result = result – 18 = 36 – 18 = 18.

এখন আমরা ৩৬ কে ২ দিয়ে যতবার ভাগ করা যায়, করে ফেলবো। এক্ষেত্রে ২ বার ভাগ করার পরে আমরা পাবো ৯।
এখন ১ থেকে ১৮ এর মাঝে ৩ এর গুণনীয়ক আছে , ১৮/৩ = ৬ টি।
তাহলে আমরা লিখবো result = result – 6 = 18 – 6 = 12.
সুতরাং, φ(৩৬) = ১২।

এরপরে আমরা আবার ৯ কে ৩ দিয়ে ভাগ করতে থাকবো। যদি আমাদের n এর মান ১ হয়ে যায়, তাহলে আমাদের আর কিছু করার দরকার নাই। কিন্তু যদি ১ না হয়, তাহলে আমরা result = result – result/n করবো, কেননা, ১ যেহেতু হয়নি, কাজেই, n আসলে প্রাইম নাম্বার ছিল। আর আমরা আগেই জানি, প্রাইম এর জন্য φ(prime) = prime-1

এতক্ষন আমরা যেসব phi জেনারেট করলাম, তার সবই সিম্পল কুয়েরির ক্ষেত্রে ভালো এবং দ্রুত আউটপুট দিবে, কিন্তু, আমাদের যদি কুয়েরির মান অনেক হয়, তাহলে বারবার phi ফাংশন কল করলে আমাদের প্রোগ্রাম TLE দিবে। এজন্য আমাদের আরও এফিশিয়েন্ট অ্যালগরিদম দরকার, যার মাধ্যমে আমরা সহজে অনেকগুলি phi এর মান আগে থেকে জেনারেট করে এরপরে কুয়েরির অ্যান্সার করবো। ঠিক সীভ (sieve of eratosthenes) যেভাবে জেনারেট করতাম, সেভাবে জেনারেট করবো। সকলের জন্য পরামর্শ রইল নিজে কোডটি লিখার। চেষ্টা করার পরে না পারলে এরপরে নিচের কোড দেখে শিখে নেয়া যাবে।

ফাইনালি, একটি সুন্দর জিনিস দেখা যাক।
For any integer n, the sum of the totient(phi) values of each of its divisors equals n”.

এখন দেখা যাকঃ
n = summation of φ( x ) ; where x are the divisors of n.
যেমন, 30 এর divisor = 

1 x 30
2 x 15
3 x 10
5 x 6
so,  30 = φ( 1 )+φ( 2 )+φ( 3 )+φ( 5 )+φ( 6 )+φ( 10 )+φ( 15 )+φ( 30 ) = 1+1+2+4+2+4+8+8 = 30
অর্থাত, যেকোন সংখ্যার সকল divisor এর phi এর মানের যোগফল, ঐ সংখ্যার সমান হবে।

Practice Problems

 

স্লাইডিং উইন্ডো (Sliding Window Technique)

প্রোগ্রামিং কন্টেস্টে আমাদের অনেক সময় ৩ বা ৪ বা এরচেয়েও বেশি লুপ এর কোড লিখতে হয়। ব্যাসিকালি ব্রুটফোর্স যাকে বলে। এখন আমরা যেই টেকনিক দেখবো, এটি এরকম একাধিক লুপ এর প্রব্লেমকে কম সময়ে সল্ভ করে দিতে পারবে। 

স্লাইডিং উইন্ডো সমস্যার বিভিন্ন রূপ আছে। কিন্তু তাদের সবারই একটি কমন বৈশিষ্ট আছে : একটি সাব-অ্যারেকে (আমরা একে ‘উইন্ডো’ বলে থাকি, যা স্ট্যাটিক বা ডাইনামিক দৈর্ঘ্য থাকতে পারে) আমরা  n সংখ্যক উপাদানগুলির অ্যারে এর বাম থেকে ডান দিকে লিনিয়ারভাবে সরায়ে কিছু কম্পিউট করার চেষ্টা করবো। এভাবে উইন্ডো স্লাইড করার টেকনিক কেই স্লাইডিং উইন্ডো বলে। স্লাইডিং উইন্ডোর অনেক রকম ভ্যারিয়েশন আছে। যেমন ঃ 

  1. একটি অ্যারের মাঝে ফিক্সড সাইজের কোন সাব-অ্যারের ম্যাক্সিমাম সামেশন বের করা। যেমন ঃ অ্যারে  A = {10, 40, 10, 30, 20} এবং উইন্ডো সাইজ w = 3 হলে, মাক্সিমাম সামেশন = 40+10+30 = 80. 
  2. একটি অ্যারের মাঝে ফিক্সড সাইজের সকল সাব-অ্যারের ম্যাক্সিমাম অথবা মিনিমাম সংখ্যা বের করা। যেমন ঃ
    অ্যারে A = {0, 5, 5, 3, 10, 0, 4} , n = 7 এবং উইন্ডো সাইজ w = 3, হলে এখানে n-w+1 = 5 টি ভিন্ন ভিন্ন সাব-অ্যারে আছে যাদের সাইজ = 3; {0, 5, 5}, {5, 5, 3}, {5, 3, 10}, {3, 10, 0}, {10, 0, 4}. এবং আমরা এদের ম্যাক্সিমাম সংখ্যা বের করতে চাইলে এগুলি হবে ঃ 5, 5, 10, 10, 10 প্রতি সাব-অ্যারের জন্যে। 
  3. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর, যার এলেমেন্ট এর সাম, নির্দিষ্ট কোন সাম থেকে বড়/ সমান/ ছোট হয়। যেমন ঃ অ্যারে A = {5, 1, 2, 3, 4, 2} এবং S = 7 হলে,
    মিনিমাম দৈর্ঘ্য == 7 : 2,  {5, 1, 2, 3, 4, 2}
    মিনিমাম দৈর্ঘ্য > 7 : 3,  {5, 1, 2, 3, 4, 2} , {5, 1, 2, 3, 4, 2}, {5, 1, 2, 3, 4, 2}
    মিনিমাম দৈর্ঘ্য < 7 : 1,  {5, 1, 2, 3, 4, 2} ; যেকোনটাই হতে পারে।
     
  4. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর যাতে  [ 1 to w ] পর্যন্ত সকল সংখ্যা কমপক্ষে একবার করে হলেও থাকবে। যেমনঃ A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} এবং w = 4, আমরা 13 length এর একটি সাব-অ্যারে পাবো, যাতে 1, 2, 3, 4 আছে। এই সেইম অ্যারের জন্যে যদি w = 3 হয়, তাহলে A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} আমরা 3 length এর একটি সাব-অ্যারে পাবো। 

সলুশন (Solution)
উপরের প্রবেল্মগুলি আমরা নরমালি বারে বারে লুপ চালায়ে সল্ভ করতে পারবো তখনি, যখন রেঞ্জ কম হবে, যা আমাদের given time এর মাঝে সল্ভ করা সম্ভব হয়। আমরা ব্রুটফোর্স এর ব্যাপারগুলি বাদ দিয়ে সরাসরি আমাদের স্লাইডিং উইন্ডো টেকনিক এ চলে আসি, যা কিনা O (n) সময়ে সল্ভ করতে সক্ষম।

১ম টেকনিক (First Technique):

আমরা প্রথমে উইন্ডো তে আমাদের প্রথম w টি ইন্টিজার ইন্সার্ট করে দিলাম এবং এদের সাম বের করে তাকে curr_sum ভ্যারিয়েবল এ রাখলাম। এরপরে আমরা স্লাইড করে করে আগাবো। আমরা ডান পাশে একটি একটি করে এলেমেন্ট উইন্ডো তে ইন্সার্ট করবো এবং বাম দিক থেকে একটি করে সরায়ে দিব, ফলে আমাদের উইন্ডোর সাইজ সেইম থাকবে।এলেমেন্ট ইন্সার্ট এর সময় আমরা চেক রাখবো যে এখন আমরা ম্যাক্সিমাম সাম পেলাম কিনা। প্রতিবার ইন্সার্ট করার সময় আমাদের নতুন সাম হবে curr_sum + inserted_element – removed_element. এভাবে আমরা পুরো অ্যারেকে স্লাইড করে রেসাল্ট পাবো। 

২য় টেকনিক (Second Technique):

যদি n এর মান অনেক বড় হয়, সকল সাব-অ্যারের মাক্স/মিন বের করা একটু কঠিন হবে। এজন্য আমরা deque (double ended queue) ব্যবহার করবো। এখন আমাদের উইন্ডো হবে আমাদের deque টি। আমরা deque কে ascending order ( ছোট থেকে বড় ) এ সাজাবো ( যদি মিন বের করতে চাই)। deque এর প্রথম দিকে আমাদের মিনিমাম এলেমেন্ট গুলি থাকবে। কিন্তু এভাবে কাজ করতে গেলে একটি বড় প্রব্লেম হল, আমাদের মূল অ্যারের ইন্ডেক্সগুলি উল্টাপাল্টা হয়ে যাবে, এজন্য আমাদের ইন্ডেক্স এর ট্র্যাক রাখতে হবে যাতে আমরা বুঝতে পারি যে, এলেমেন্ট উইন্ডো তে আছে কি নাই। নিচের একটি স্যাম্পল কোড দেয়া হল ঃ 

৩য় টেকনিক (Third Technique):

আমরা একটি ডাইনামিক সাইজ উইন্ডো মেইন্টেইন করবো, যেখানে ভ্যালু যোগ করতে থাকবো। মিন/ ম্যাক্স/ ইকুয়াল, কোন এক কন্ডিশন পেলে আমরা আমাদের মিনিমাম উইন্ডো সাইজ পেয়ে যাবো। প্রোগ্রাম এ কি চাওয়া হয়েছে তার উপরে ভিত্তি করে আমাদের কোড এ কন্ডিশন এর পরিবর্তন হবে। এখানে আমরা ১ম টেকনিক এর মত করে ইন্সার্ট করতে থাকবো এবং কন্ডিশন চেক করবো। আর এলেমেন্ট উইন্ডোতে আছে কিনা, উইন্ডো সাইজ কি আমাদের মূল অ্যারে থেকে বড় হয়ে গেলো কিনা – এসব আমরা ২য় টেকনিক এর মত একটি deque নিয়ে চেক করতে পারি।

৪র্থ টেকনিক (Fourth Technique):

আমরা এমন একটি উইন্ডো মেইন্টেইন করবো যা কিনা 1 to w সকল সংখ্যা যদি না পাই, উইন্ডো সাইজ বারাতে থাকবে, নাহলে সাইজ কমাতে থাকবে। আমরা মিনিমাম উইন্ডো সাইজের ট্র্যাক রাখবো। 1 to w সকল এলেমেন্ট পেয়ে গেলাম কিনা এটি আমরা নরমাল একটি ফ্রিকুয়েন্সি কাউন্টের মাধ্যমে করতে পারি। যখন সকল এলেমেন্ট এর কাউন্ট >0 হবে, তখন আমরা আমাদের মিনিমাম উইন্ডো সাইজ রিটার্ন করে দিবো।

প্র্যাক্টিস প্রব্লেম (Practice Problems): 

LightOj: Algebraic Problem

Problem Link: loj1070
Technique: Matrix Exponentiation

Given the value of a+b and ab you will have to find the value of an+bna and b not necessarily have to be real numbers. I solved this using matrix exponentiation technique. I will now write about how I modelled the base matrix for multiplication. There may be other approaches too. But first please read this blog if you don’t know about how to create a matrix from a recurrance relation.

First let’s observe some cases.
If n = 0, a0+b= 1+1 = 2
If n = 1, a1+b= a+b – 0
If n = 2, a2+b= (a+b) (a+b) – 2ab
If n = 3, a3+b= (a+b) ( (a+b)– ab ) – 2ab (a+b)
…………..     …………..     ………….     ……………..

So, basically the recurrence somehow turns like this –>

(a1+b1) = (a+b) + (-0)
(a2+b2) = (a+b) (a+b) + 2(-ab)
So,
base  =  | (a+b)   -ab  |
            |   1           0   |

We will multiply (a+b) with base [0][0] and 2 with base [0][1], then we will get our final output by summing these two elements.

So, when n = 0 , ans will be 2.
When n = 1, ans will be a+b
When n = 2, ans will be (base)= (a+b) * (a+b) + 2 * (-ab) = (a+b)2 – 2ab
When n = 3, ans will be (base)2  = (a+b) * [(a+b)2 -ab)] + 2 * [-ab*(a+b)]

Let’s see this : (for n = 3)
yo.jpg
In our base matrix, after performing exponentiation, at base [0][0] we get [(a+b)2 -ab)], and we will multiply it with (a+b). Similarly, at base[0][1] we get [-ab*(a+b)], so we will multuply it with 2. And by summing these two elements, we will get our final output.

NOTE : As For each test case, print the case number and (an+bn) modulo 264, we will use unsigned long long for each variable instead of applying modulus operation. This will save our time. Infact, without this, the program will get TLE.

“Don’t directly copy code. First try to understand how each step works, then do your own coding.”

A* Search Algorithm for N-Puzzle

আমরা A* সার্চ দিয়ে ৮-পাযল প্রব্লেমটি সল্ভ করার চেষ্টা করবো। শুরুতে একটি স্ট্রাকচার এ আমরা আমাদের স্টেট সেইভ রাখার জন্য স্ট্রিং, পাথ সেইভ রাখার জন্য আরেকটি স্ট্রিং, হিউরিস্টিক, ডেপথ এসব সেইভের জন্য ইন্টিজার। তাহলে স্ট্রাকচার এমন দাঁড়ায় ঃ
struct puzzle {
string state, path;
int heuristic, depth, f;
}
আমরা f এর মাঝে depth + heuristic সেইভ রাখবো প্রতিটি স্টেট এর জন্য। এখন আমাদের কাজ হচ্ছে একটি প্রায়োরিটি কিউ নেয়া। প্রায়োরিটি কিউ তে আমরা f এর মান অনুসারে নোড ইনসার্ট করবো। তাহলে যার f এর মান কম, সেটি আমরা আগে প্রসেস করবো।

আমরা ইনিশয়াল এ আমাদের স্টেট এর পাথ এর জন্য “0” পুশ করতে পারি path স্ট্রিং এ, depth হবে 0 এবং f এর মান হবে, depth + heuristic = ( হিউরিস্টিক হিসাব করে যত হয়, আমরা তা বসাবো )।
চাইল্ড নোড জেনারেট এর পরে, চাইল্ড এর ক্ষেত্রে depth = parent.depth + 1 এবং path এর ক্ষেত্রে আমরা যদি UP ,মুভ দেয়ার ফলে চাইল্ডটি পেয়ে থাকি, তাহলে path = parent.path + “U” এভাবে পুশ করে দিবো।
আমরা যদি আমাদের ফাইনাল স্টেট পেয়ে যাই, তাহলে আমরা path স্ট্রিংটি রিটার্ন করে দিবো, এবং এই path থেকে পরবর্তীতে আমরা ইনিশিয়াল থেকে ফাইনাল স্টেট এর গ্রিড ও প্রিন্ট করতে পারবো।

২ টি ভেক্টর নিবো open এবং close নামের। open এর কাজ হচ্ছে, আমরা যেসব নোড এখনও এক্সপান্ড করিনি, সেগুলি রাখবো। আর close এর মাঝে আমরা, যেসব নোড এর এক্সপান্ড হয়ে গেছে,সেগুলো রাখবো।open, close এর কাজ হল, অপ্রয়োজনীয় নোড নিয়ে আমাদের মাথা ব্যথা আর করা লাগবেনা। আমরা প্যারেন্ট নোড থেকে চাইল্ড বানানোর পর দেখবো যে, এই চাইল্ড আগে থেকেই open এর মাঝে আছে কিনা, যদি থাকে, এবং ঐ open এর চাইল্ড যদি আমাদের এখন পাওয়া চাইল্ড এর চেয়ে ভালো অথবা সমান হয়, তাহলে আমরা এখনকার চাইল্ড আর নোড এ পুশ করবোনা। একই কাজ আমরা close এর খেত্রেও করবো।
আর এরকম কিছু না হলে আমরা সেটি কিউ তে পুশ করবো। এভাবে কাজ চলতে থাকবে, এবং আমরা আমাদের ফাইনাল স্টেট পেলে ব্রেক করে দিবো আর পাথ এর স্ট্রিংটি থেকে আমরা ইনিশিয়াল থেকে সহজেই পাথ ও প্রিন্ট করতে পারবো।

psudocode :  A* search
path_finding : Path

Searching Algo

লিনিয়ার সার্চ(Linear Search)

লিনিয়ার সার্চ সবচেয়ে ব্যাসিক সার্চ টেকনিক। ধরি আমাদের n টি নম্বর এর একটি অ্যাারে দেয়া আছে। এখন আরেকটি নম্বর a দিয়ে আমাকে জিজ্ঞাসা করা হল, এই a , আগের n টি নম্বর এর মাঝে আছে কিনা। স্বাভাবিকভাবে আমরা 0 থেকে n (অ্যাারে এর ঘর বিবেচনা করলে) পর্যন্ত একটি লুপ চালায়ে নম্বরটিকে বের করার চেষ্টা করবো।

int arr [ ] = { 1, 2, 4, 12, 14, 78, 21, -90, 111, 1467};
int a = 111;
for ( int i = 0; i < 10; i++ ){
          if ( arr [ i ] == a ){
                cout << ” Found the number 😀 ” << endl;
                break;
}
}
সার্চিং এর ক্ষেত্রে লিনিয়ার সার্চ ছোট রেঞ্জ এর মধ্যে কাজ করবে কিন্তু রেঞ্জ বড় হয়ে গেলে TLE দিবে। আমরা লিনিয়ারি একটি পজিশন থেকে আরেকটি পজিশন এ যাচ্ছি ( n তম এলেমেন্ট পাওয়ার জন্য আমাদের শুরু থেকে n পর্যন্ত যেতে হবে), কাজেই লিনিয়ার সার্চের কমপ্লেক্সিটি O ( n )  [ Order of n ] যেখানে n হল কতটি এলেমেন্ট এর মাঝে সার্চিংটি চলছে।

বাইনারি সার্চ(Binary Search)

বাইনারি সার্চ সবচেয়ে জনপ্রিয় সার্চ টেকনিক এবং এর ব্যবহার ও খুব মজার। বাইনারি সার্চের জন্য প্রথমেই আমাদের নম্বরগুলিকে কোন একটি অর্ডার এ সাজাতে হবে ( Ascending or Descending )। এরপরে আমরা ২টি পজিশন সেট করবো low এবং high নামে। low  হবে আমাদের অ্যাারে এর 0th ইনডেক্স এবং high হবে (n-1)th ইনডেক্স। এখন আমরা এই high এবং low এর মাঝে থেকে middle ইনডেক্স বের করার চেষ্টা করবো এবং চেক করবো ঐ middle ইনডেক্স এর ভ্যালুটা আমাদের কাঙ্ক্ষিত ভ্যালুর সাথে মিলে গেছে কিনা। যদি মিলে যায়, তাহলে আমরা আমাদের ভ্যালু পেয়ে গেছি। যদি না মিলে, তবে ২টি কন্ডিশন হতে পারে।
১ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে বড়।
২ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে ছোট।
ধরি আমাদের অ্যাারেটি ছোট থেকে বড় আকারে সাজানো আছে। এখন ১ এর জন্য মিড ভ্যালুটি বড়, কাজেই আমাদের কাঙ্ক্ষিত ভ্যালুটি মিড ইনডেক্স এর অবশ্যই আগে আছে। কাজেই তখন আমাদের high হয়ে যাবে middle – 1 এবং low এর কোন চেঞ্জ হবেনা। ২ঃ এর খেত্রেও একই ব্যাপার। তখন low হবে middle + 1 এবং high এর কোন চেঞ্জ হবেনা। একটি উদাহরন দেখিঃ আমাদের ২০ কে খুঁজে বের করতে হবে। binary-search
টাইম কমপ্লেক্সিটি ঃ আমরা প্রতিবার সার্চিং এর জন্য একটি অংশ নিচ্ছি এবং অন্যটি বাদ দিয়ে দিচ্ছি। কাজেই worst case এর জন্য আমাদের কমপ্লেক্সিটি হবে O ( N * logN )।
স্যাম্পল কোড ঃ Capture
আমরা ভ্যালু পেয়ে গেলে ভ্যালুটির ইনডেক্স রিটার্ন করবো, আর না পেলে -1 রিটার্ন করবো। লক্ষ্য করলে দেখবে যে বাইনারি সার্চ এর টারমিনেট কন্ডিশন যখন high এর চেয়ে low এর ইনডেক্স বড় হয়ে যাবে। এই ব্যাপারগুলি ভালোভাবে খেয়াল না রাখলে ইনফিনিট লুপ এ পরবে প্রোগ্রাম। কোড করার সময় তাই আমাদের মাথায় রাখতে হবে আসলে কখন কোথায় কি হচ্ছে এবং কখন কোন কন্ডিশন দিলে ঠিকমতন প্রোগ্রাম রান করবে।

 

Prime Numbers (sieve of Eratosthenes)

প্রাইম  (Prime ) সংখ্যা বলতে আমরা বুঝি এমন সংখ্যা যাকে ঐ সংখ্যা যার শুধুমাত্র ২ টি ফ্যাক্টর ( ১ এবং সংখ্যাটি নিজে ) আছে। অর্থাৎ যেসব সংখ্যাকে ঐ সংখ্যা এবং ১ ছাড়া আর কোন সংখ্যা দিয়ে ভাগ করা যায়না। যেমনঃ ২, ৩, ৫, ৭,… এগুলো প্রাইম সংখ্যা। আবার ৮ কিন্তু প্রাইম না, কারন ৮ এর ফ্যাক্টর ১, ২, ৪, ৮। প্রাইম ছাড়া যেসব সংখ্যা আছে, তাদেরকে বলা হয় কম্পোজিট (Composite) সংখ্যা।

প্রাইম এবং কম্পোজিট সংখ্যার জ্যামিতিক ব্যাখ্যা

প্রাচীনকালের গনিতবিদরা, বিশেষ করে গ্রীক গনিতবিদরা সবসময় সংখ্যাকে জ্যামিতিক ব্যাখ্যা আকারে উপস্থাপন করার চেষ্টা করতেন।যেমন বর্গ সংখ্যাগুলোকে একই সংখ্যক সারি এবং কলাম আকারে ছোট ছোট পাথরের মাধ্যমে সাজানো হত। প্রথম পাঁচটি বর্গ সংখ্যা ১, ৪, ৯, ১৬, ২৫।
আয়তাকার সংখ্যারাও অনেক জনপ্রিয়। যেমন ধরা যাক, ১২ কে নিম্নোক্ত উপায়ে আয়তাকারভাবে ছোট ছোট পাথর এর মাধ্যমে দেখানো যায়ঃ
11

দেখা যাচ্ছে, ১২ কে ৩ রকমভাবে আয়তাকার আকারে সাজানো যায়।
যেসব সংখ্যাকে ১ এর বেশি আয়তাকার আকারে সাজানো যায় না, তাদেরকে প্রাইম সংখ্যা বলে। যেমন, ৩, ৫, ৭ কে শুধু একটিমাত্র সারি তে সাজানো যায়ঃ
13
কাজেই, জ্যামিতিকভাবে লক্ষ্য করলে আমরা দেখতে পাই যে প্রাইম সংখ্যার শুধুমাত্র ১ এবং ঐ সংখ্যা ছাড়া আর কোন ফ্যাক্টর নেই।

১ কি প্রাইম ?

ফরমালি আমরা যা শিখলাম, তাতে ১ কে প্রাইম ভাবাই স্বাভাবিক। কারন, ১ কে ১ দিয়ে ভাগ করা যায়, এবং ১ নিজেও নিজেকে দিয়ে ভাগ যায়। অবশ্য যদি আরেকভাবে খেয়াল করি, তাহলে কিন্তু ১ এর ফ্যাক্টর আসলে শুধু ১ ই, তাই এ হিসাবে আবার প্রাইম নাও বলা যায়! আসলে তাহলে ব্যাপারটা কি? আমরা নিচে এর একটা সুন্দর ব্যাখ্যা দিবো, এতে আশা করি আর সমস্যা থাকার কথা না।

সীভ অফ ইরাটোস্থেনেস(sieve of Eratosthenes)

গ্রীক দার্শনিক এবং গনিতবিদ ইরাটস্থেনেস সবার প্রথম একটি সসীম ধারায় প্রাইম সংখ্যাগুলোকে ব্রুট ফোর্স ( Brute force ) আকারে লিখতে সক্ষম হন।

তার নামানুসারে এইভাবে প্রাইম সংখ্যা বের করার অ্যালগরিদমটির নাম হল sieve of Eratosthenes.  এই অ্যালগরিদমটির মাধ্যমে আমরা ১০ কোটির নিচের সকল প্রাইম সংখ্যা খুব অল্প সময়ের মধ্যে বের করে ফেলতে পারি।
sieve শব্দের অর্থ হল ছাকনি যা অপ্রয়োজনীয় অংশ ছেটে ফেলে।

12

আমরা এই টেবিলটি খেয়াল করি। ধরি আমার ১ থেকে ১০০ এর মধ্যে কিকি প্রাইম সংখ্যা আছে, তা সীভ অ্যালগো ব্যবহার করে বের করতে হবে। এখন সীভ এর ব্যাপারটা হচ্ছে, শুরু থেকে এক এক করে সকল সংখ্যা দেখতে দেখতে সামনে এগিয়ে যেতে হবে। সামনে আগানোর পথে যখনি আমরা কোন সংখ্যা পাবো যাকে আগে পাইনি, সেটা আমরা কেটে ফেলে দিবো। এখন প্রথমে আমি ১ বাদ দিয়ে ২ থেকে যাত্রা শুরু করবো (১ কেন বাদ দিলাম, তা একটু পরে তোমরা নিজেরাই বুঝে যাবে)। এখন ২ যেহেতু আগে পাইনি তাই ২ প্রাইম হিসেবে মার্ক করে রাখবো, এরপরে আমরা প্রাইম এর একদম বেসিক আইডিয়া থেকে যা জানি, একটা সংখ্যা যদি প্রাইম হয়, তাহলে ঐ সংখ্যার চেয়ে বড় ঐ সংখ্যার সকল গুনিতক কে আমরা প্রাইম থেকে বাদ দিয়ে দিতে পারি। কেননা ঐ বড় সংখ্যাগুলো অবশ্যই ঐ সংখ্যা দিয়ে ভাগ যাবে, ফলে এগুলো প্রাইম হিসেবে নেয়া যাবেনা। যেমন ২ এ আসার পরে আমরা ২ এর পরের ২ এর গুনিতকগুলো যেমন ৪, ৬, ৮, … এভাবে ১০০ পর্যন্ত সব কেটে দিবো। এরপরে আমরা আবার আগের জায়গায় ফিরে আসি। আগে আমরা ২ এ ছিলাম, এখন আমরা যাবো ৩ এ। যেহেতু ৩ কাটা পড়েনি, তাই ৩ কে প্রাইম হিসেবে মার্ক করবো এবং ৩ এর চেয়ে বড় ৩ এর গুনিতকগুলি কেটে দিবো। এরপরে কাজ শেষে আবার আমরা আসবো ৪ এ। এখন এই ৪ কিন্তু ২ এর সময় কাটা পড়ে গিয়েছিল, কাজেই আমরা ৪ কে বাদ দিয়ে সামনে আগাবো, কারন আমরা জানি, ৪ প্রাইম না। এভাবে করে আগালে আমরা সুন্দরভাবে প্রাইম সংখ্যাগুলি পেয়ে যাবো। আশা করি সবাই এতক্ষণে বুঝে ফেলেছো কেন আমরা ১ থেকে যাত্রা শুরু করিনি। ১ থেকে যদি যাত্রা শুরু করতাম, তাহলে সীভ মেথড অনু্যায়ী ১ কে আমরা প্রাইম হিসেবে মার্ক করতাম, এবং এরপরে ১ এর চেয়ে বড় ১ এর সকল গুনিতক কে কেটে ফেলতাম! তাহলে আর সংখ্যাই তো থাকলো না !! এজন্যে ১ কে প্রাইম হিসেবে ধরা হয়না। অবশ্য কোন কোন জায়গায় ১ কে প্রাইম হিসেবে ধরতেও পারে। আমরা যারা কন্টেস্ট প্রব্লেম সল্ভ করি, প্রশ্নে যদি ১ কে প্রাইম ধরে কাজ করতে বলা হয়, তাহলে তাই করতে হবে, নাহলে আসলে ১ কে প্রাইম ধরা অযৌক্তিক।
আমরা যদি দেখতে চাই, N একটি প্রাইম কিনা, তাহলে আমাদের কি আসলেই N-1 পর্যন্ত সংখ্যা বিবেচনায় আনার দরকার আছে? একটু খেয়াল করলে দেখতে পারবো যে, আমরা যদি N/2 পর্যন্ত সংখ্যা চেক করি, তাহলেই কাজ হয়ে যাচ্ছে। এখন N/2 এর চেয়েও আরো ভাল একটি উপায় হল √N ( square root of N )। 

কেন স্কয়ার রুট অফ N ? ( Why square root of N? ) 

ধরি আমরা 24 এর জন্য চেক করবো সংখ্যাটি প্রাইম কিনা। এরজন্য আমাদের √24 = 4.89897948557 ≅ 4
অর্থাৎ আমাদের মাত্র 4-1=3 টি সংখ্যা চেক করলেই আমরা বলতে পারবো 24 প্রাইম কিনা। এই 3 টি সংখ্যা হবে 2,3,4.
আমরা 1 কে বিবেচনায় রাখিনি, তাই 1 বাদ যাবে। কেন এই স্কয়ার রুট কাজ করে তার জন্য আমরা যদি 24 এর ফ্যাক্টর গুলি বের করি, তাহলে বুঝতে পারবো।
Capture.JPG
খেয়াল করলে দেখবো যে, 24 এর উৎপাদকগুলির মাঝে আমরা যদি 4 পর্যন্ত চেক করি, তাহলেই সব সংখ্যা চেক করা হয়ে যাচ্ছে।মানে 24 একবার 2 দিয়ে ভাগ গিয়েছে, কাজেই আবার 12 দিয়ে ভাগ দেয়ার কোন দরকার নেই। আর 24 এর স্কয়ার রুট হচ্ছে 4। কাজেই স্কয়ার রুট পর্যন্ত হিসাব করা আমাদের জন্য ভালো অপশন।

সুডোকোডঃ

Capture.JPG
সীভ অ্যালগরিদম এর টাইম কমপ্লেক্সিটি O ( n log n)।