UVA 106 : Fermat vs. Pythagoras

প্রবলেমঃ 

তোমাকে একটি ইন্টিজার n দেয়া হবে। তোমাকে  n থেকে ছোট সেসব Pythagorean Triples এর সংখ্যা বের করতে হবে, যারা Relatively Prime, অর্থাৎ যাদের GCD (Greatest Common Divisor বা গ.সা.গু ) ১। তোমাকে আরো বের করতে হবে n থেকে ছোট কোন কোন Integer গুলো কোন Triple এই থাকবে না, তাদের সংখ্যা (এই অংশের জন্য রিলেটিভ প্রাইম না হলেও কাউন্ট করতে হবে)।

যদি ইনপুট এমন হয়,

10
25
100

আউটপুট হবে এমনঃ

1 4
4 9
16 27

প্রত্যেক আউটপুটের দু’টি Portion। ইনপুট 10 এর জন্য ব্যাখ্যা করছি। প্রথম Portion এর জন্যঃ- ১ থেকে ১০ পর্যন্ত শুধু একটি Pythagorean Triple – ই আছে যারা রিলেটিভলি প্রাইম। এরা হল (3, 4, 5)। তাই আউটপুটে 1। আরেকটি Pythagorean Triple আছে (6,8, 10), যারা Relatively Prime না, অর্থাৎ টোটাল ৬ টি নাম্বার আছে ১ থেকে দশের মধ্যে, যারা কোন না কোন Pythagorean Triple এর অংশ (3, 4, 5, 6, 8, 10)।  চারটি নাম্বার (1, 2, 7, 9) কোন ট্রিপলেই জায়গা পায়নি, তাই আউটপুটের দ্বিতীয় অংশে 4 এসেছে।

প্রবলেম লিঙ্কঃ UVA 106

  • যদিও প্রবলেমে বলা আছে, input এ n সর্বোচ্চ 1000 হতে পারে, কিন্তু discuss থেকে দেখা যায়, n এর ভ্যালু সর্বোচ্চ 10^6 হতে পারে। এই ভুল স্টেটমেন্টের কারণে কয়েকটি রানটাইম এরর পেয়েছি। 😦 Solution টার Time Complexity ও খুব বাজে ছিল। পরে Discuss থেকে জানতে পারি n<=10^6 হতে পারে।

কিভাবে করব?

ধরে নিই, (a, b, c) একটি Pythagorean Triple হলে,

a^2 + b^2 = c^2 

Pythagorean Triple এর একটি মজার ব্যাপার হল,  (a, b, c) যদি কোন Pythagorean Triple হয়, তবে এটাও সত্য যে (ka, kb, kc) ও Pythagorean Triple হবে, যেখানে k একটি Positive Integer। যেমন, (3, 4, 5) যেহেতু Pythagorean Triple, তাই (6 , 8 , 10 ), (9 , 12 , 15 ), (12, 16, 20) …. এভাবে যেকোন k-গুণিতকের জন্য এটা সত্য।

তাই এই প্রবলেমের ক্ষেত্রে আমার আইডিয়া হচ্ছে, যখনই কোন Pythagorean Triple পাব, সেই Pythagorean Triple এর সাথে সাথে n পর্যন্ত সব k গুণিতক Pythagorean Triple এর নাম্বারগুলোকেও মার্ক করে রাখব। এখন না বুঝলেও প্রবলেম নাই, আশা করি, পুরো পোস্ট পড়ার পর Solution ক্লিয়ার হয়ে যাবে, ইনশা’আল্লাহ। 🙂

প্রশ্ন হচ্ছে, আমি সেসব Pythagorean Triple কিভাবে পাব, যারা Relatively Prime? এর জন্য প্রথমে আমার কিছু জিনিষ দেখে নিইঃ

  1. যেহেতু Pythagorean Triple হবে Relatively Prime, তাই a, b & c এর তিনটিই কখনো even হওয়া সম্ভব না। কারণ, তাহলে আর এই ট্রিপলটি Relatively Prime থাকেনা।
  2. শুধু a & b ও ইভেন হতে পারে না, কারণ তাহলে a^2 & b^2 এর যোগফলও ইভেন হয়ে যাবে।
  3. a & b এর যেকোন একটি জোড় কিন্তু a^2 এবং b^2 এর যোগফল জোড়, এমনও হওয়া পসিবল না, কারণ জোড় নাম্বারের স্কয়ার এবং বিজোড় নাম্বারের স্কয়ারের যোগফল কখনো জোড় হতে পারে না।
  4. উপরের ২ ও ৩ থেকে বলতে পারি, Pythagorean Triple এর যেকোন দু’টি ও জোড় হতে পারে না।
  5. এই পয়েন্টটাই সবচেয়ে Important, তাই আলাদা করে পরে নিচে ব্যাখ্যা করছি। পয়েন্টটা হচ্ছে, a & b দু’টোই একত্রে কখনো বিজোড় হতে পারবে না।

৫ নং পয়েন্টের ব্যাখ্যাঃ 

আমাদের Pythagorean Triple যদি (a, b, c) হয়, তাহলে a^2 + b^2 = c^2। এখন যদি, a & b উভয়ই বিজোড় হয়, তাহলে এদের প্রত্যেকের বর্গের যোগফল অবশ্যই জোড় হবে। ধরি,

a=2x+1
b=2y+1
c=2z

তাহলে,

a^2 + b^2 = c^2 
=> (2x+1)^2  + (2y+1)^2 = (2z)^2 
=> 4x^2 + 4x + 1 + 4y^2 + 4y +1 = 4z^2
=> 4x^2 + 4y^2 + 4x + 4y +2 = 4z^2
=> x^2 + y^2 + x + y + \frac { 1 }{ 2 } = z^2

উপরের সমাধান থেকে দেখা যায়, a & b যদি উভয়ই বিজোড় এবং c জোড় হয়, তাহলে a, b & c -> একত্রে সবাই Integer বা পূর্ণ সংখ্যা হতে পারে না। কিন্তু Pythagorean Triples হতে হলে তো a, b & c সবাইকেই পূর্ণ সংখ্যা হতে হবে। অর্থাৎ, a & b যদি উভয়ই বিজোড় এবং c জোড় – এমন সম্ভব না। আরো ব্যাখ্যার জন্য, math.stackexchange.com এর এই প্রশ্ন ও তার উত্তরগুলোদেখতে পার। 🙂

আমরা এতক্ষণে এই সিদ্ধান্তে আসলাম যে, a & b এর মধ্যে যেকোন একটি জোড় হতেই হবে, ধরে নিই, a জোড়। তাহলে a^2 +b^2 = c^2 কে এভাবে লিখি,

a^2 = c^2 - b^2 

একে আবার লিখা যায়,

a^2 = (c+b) * (c-b) 

যেহেতু, a একটি জোড় সংখ্যা,  a^2 অবশ্যই 4 দ্বারা বিভাজ্য। আবার (c + b) & (c – b) ও জোড় সংখ্যা, কারণ দু’টি বিজোড় সংখ্যার যোগ/বিয়োগ সবসময়ই জোড় হবে। তাই উপরের Equation কে এভাবে লিখা যায়,

{(\frac { a }{ 2 } )}^2 = (\frac { c+b}{ 2 }) * (\frac { c-b}{ 2 } ) 

উপরের Equation এ  (\frac{c+b}{2}) এবং  (\frac{c-b}{2}) অবশ্যই Relatively Prime। কারণ, তারা যদি Relatively Prime না হয়, তাহলে c & b এর Relatively Prime হওয়া সম্ভব না। আরো ব্যাখ্যার জন্য math.stackexchange.com এর এই প্রশ্ন ও তার উত্তরগুলো দেখতে পার।

এখন দেখ, উপরের Equation এ একটি বর্গ সংখ্যাকে এমন দু’টি সংখ্যার গুণফল আকারে দেখানো হয়েছে, যারা কিনা আবার Relatively Prime। এ থেকে আমরা বলতে পারি,  (\frac{c+b} {2}) এবং  (\frac{c-b} {2}) – এদের প্রত্যেকেই আসলে একটি বর্গ সংখ্যা। নিচে এর ব্যাখ্যা দিচ্ছিঃ

দেখ, একটি বর্গ সংখ্যাকে যখন প্রাইম ফ্যাক্টরাইজেশন করবে, দেখবে যে, প্রাইম ফ্যাক্টরগুলো জোড় সংখ্যকবার আছে। যে কোন বর্গ সংখ্যার জন্য আগের বাক্যটি সত্য। যেমনঃ ১০০ (১০ এর বর্গ) এর প্রাইম ফ্যাক্টর ২ এবং ৫। এখন ১০০ তে ২ আছে ২ টা, ৫ আছে ২ টা। এভাবে, তুমি যেকোন বর্গের প্রাইম ফ্যাক্টরগুলো ঐ বর্গ সংখ্যায় কতবার আছে, সেটি দেখ। দেখবে, সেই সংখ্যাগুলো সবসময় জোড় হবে। (আচ্ছা, এমন কেন হয়? চিন্তা কর। 🙂 ঘনের ক্ষেত্রে কি হবে? বা অন্যান্য পাওয়ারের ক্ষেত্রে? )

এখন যেহেতু   (\frac{c+b} {2}) এবং  (\frac{c-b} {2}) Relatively Prime, অর্থাৎ এদের মধ্যে ১ ছাড়া কোন কমন ফ্যাক্টর নেই, তাই  {(\frac{a}{2})}^2 কে বর্গ বানাতে হলে,   (\frac{c+b} {2}) এবং  (\frac{c-b} {2}) এদের প্রত্যেকের প্রাইম ফ্যাক্টরগুলো জোড় সংখ্যক থাকতে হবে। অন্যথায়  {(\frac{a}{2})}^2 এর প্রাইম ফ্যাক্টরগুলো জোড় সংখ্যক থাকবে না।

এখন যদি r^2 এবং s^2 যেকোন  ধণাত্মক পূর্ণ সংখ্যার বর্গ হয়,  ধরি,

 r^2=  (\frac{c+b} {2}) 
 s^2= (\frac{c-b} {2}) 

উপরের দু’টা Equation সল্ভ করলে পাই,

c=r^2+s^2
b=r^2-s^2

a^2 +b^2 = c^2 -> এই equation এ উপরের b & c এর মান বসিয়ে পাই,

a=2*r*s

অর্থাৎ,

a=2*r*s
b=r^2-s^2
c=r^2+s^2

যেহেতু  \sqrt [ 2 ]{ 1000000}  = 1000 , তাই আমরা ইজিলি সব r, s পেয়ারের জন্য Pythagorean Triple বের করে তাদের k গুনিতকদেরকেও মার্ক করে রাখব। নিচে কোডটি দেয়া হলঃ

#include<stdio.h>
#include<math.h>

#define sz 1000010

int a[sz];

int gcd(int a, int b)
{
     int tmp;
     while(b!=0)
     {
         tmp=b;
         b=a%b;
         a=tmp;
     }
     return a;
}

int main()
{
     int i,j,x,y,z,n,cnt,sm,sq,tmpX,tmpY,tmpZ;
     while(~scanf("%d",&n))
     {
         for(i=1;i<=n;i++)
         a[i]=0;

         cnt=sm=0;

         sq=sqrt(n);
         if(sq*sq<n)
         sq++;

         for(i=1;i<=sq;i++)
         {
             for(j=i+1;j<=sq;j++)
             {
                 if(gcd(i,j)==1)
                 {
                     x=j*j-i*i;
                     y=2*j*i;
                     z=j*j+i*i;
                     if(z>n)
                     break;

                     if(gcd(gcd(x,y),z)==1)
                         cnt++;

                     tmpX=x,tmpY=y,tmpZ=z;
                     // marking the Pythagorean Triples
                     while(tmpZ<=n) 
                     {
                          a[tmpX]=a[tmpY]=a[tmpZ]=1;
                          tmpX+=x;
                          tmpY+=y;
                          tmpZ+=z;
                     }
                 }
             }
         }
         // Count those numbers what are part of any triple
         for(i=1;i<=n;i++)
         {
             if(a[i])
             sm++;
         }
         printf("%d %d\n",cnt,n-sm);
     }
     return 0;
}

প্রায় দুই বছর পর আরেকটা পোস্ট লিখলাম। ভুল থাকা অস্বাভাবিক না। 😛 কেউ সেগুলো শুধরে দিলেই খুশি হব। আর চেষ্টা করেছি ডিটেইলস লিখার, যাতে একদম বিগিনারদেরও বুঝতে সমস্যা না হয়। হয়ত কিছু কিছু ব্যাপার আরো explain করা উচিত ছিল, যেটা করতে পারিনি। এমন কোন সমস্যায় পড়লে কমেন্টে জানানোর অনুরোধ রইল। চেষ্টা করব, ব্যাখ্যা দেয়ার। 🙂

 

“HappY CodiNg ………………………………………………”

Advertisements

মন্তব্য করুন

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / পরিবর্তন )

Twitter picture

You are commenting using your Twitter account. Log Out / পরিবর্তন )

Facebook photo

You are commenting using your Facebook account. Log Out / পরিবর্তন )

Google+ photo

You are commenting using your Google+ account. Log Out / পরিবর্তন )

Connecting to %s