106 - The equation
يكشنبه, ۱۰ فروردين ۱۳۹۳، ۰۶:۳۷ ب.ظ
لینک سوال
مفهوم سوال
سوال به ما یه معادله به فرم a * x + b * y + c = 0 میده و از ما خواد ببینیم چند از جوابهای صیحی اون تو شرط x1 <= x <= x2 و y1 <= y <= y2 صدق می کنند ؟
سوال به عنوان ورودی به ما a , b , c , x1 , x2 , y1 , y2 رو میده و از ما تعداد جوابهارو می خواد .
قدرمطلق همه اعداد کوچکتر از 108 است .
حل
اگر به صورت هندسی نگاه کنیم سوال از ما تعداد تقاطی از مشبکه اصلی ( دستگاه مختصات ) رو می خواد که داخل یا روی یک مستطیل داده شده اند .
مساله رو به چند قسمت تقسیم می کنیم :
اگر a = b = 0 باشه تو این حالت معداله تبدیل به یک نقطه میشه . حالا اگر c = 0 باشه ، تمام مستطیل داده شده جواب هستند و اگر نباشه مساله جواب نداره .
اگر a = 0 باشه ، معادله تبدیل میشه به b * y + c = 0 یا y = -c / b .
تو این حالت اگر خط y = -c / b مقداری صحیح داشته باشه ، مساله x2 - x1 + 1 جواب خواهد داشت وگرنه معادله بی جواب خواهد بود .
اگر b = 0 باشه به خط x = -c / a می رسیم و بسته به شرایط یا y2 - y1 + 1 جواب داریم یا جواب نداریم .
اگر a , b صفر نباشند .
برای بدست آوردن جواب ، یک جواب دلخواه رو در نظر می گیریم مثلا (x , y )
براحتی میشه دید که ( x+b , y-a ) هم یک جواب برای معادله هستند .
برای شمردن تعداد جواب ها اول دو ضلع عمودی مستطیل رو در نظر می گیریم .
کمترین تعداد shift لازم برای اینکه جواب دلخواه بین دو ضلع بیوفته رو بدست میاریم . اسمش رو L1 می زاریم .
همچنین بیشترین shift برای اینکه بین دو ضلع بیوفته رو بدست میاریم . اسمش رو R1 می زاریم .
حالا دو ضلع افقی مستطیل رو در نظر می گیریم .
کمترین و بیشترین تعداد shift برای بین دو ضلع موندن جواب دلخواه رو L2 , R2 می نامیم .
جواب مساله میشه min( R1 , R2 ) - max( L1 , L2 ) + 1
البته ممکنه مطاله جواب صحیح نداشته باشه ، تو این حالت عبارت فوق جواب منفی میده !!
برای بدست آوردن این مقادیر به صورت زیر کار می کنیم .
مثلا برای بدست آوردن L1 :
برای بدست آوردن جواب دلخواه می تونیم از Extended GCD استفاده کنیم .
این الگوریتیم جوابی برای معادله a * x + b * y = g به ما میده ، با ضرب طرفین در c / g یک جواب برای معادله اصلی خواهیم داشت .
حالا با داشتن یک جواب معادله می تونیم L1 رو حساب کنیم .
L1 = ( x1 - x ) * g / b ;
البته باید حواسمون باشه که اگر x1 - x ) * g ) به b بخشپذیر نباشه ، این رابطه اولین نقطه قبل از دو ضلع رو میده !!
مهسا