ای سی ام کار تازه وارد

لینک سوال

مفهوم سوال

سوال میگه (d(n رو n + مجموع ارقام عدد n تعریف می کنیم .

عدد n رو یک سازنده عدد (d(n میگیم .

عددهایی که هیچ سازنده ای ندارند رو Self Number میگیم .

سوال به ما لیستی شامل k اندیس رو میده و self number متناظر با اندیس هارو از ما می خواد .

N < 10⁷ و k < 5000

حل

کافیه همه self number هارو غربال کنیم .

از 1 شروع می کنیم و اگر عددی سازنده نداشت ( مارک نشده بود ) ، به لیست اضافه می کنیم .

همچنین برای هر عدد (d(n رو مارک می کنیم .

برای اینکه سرعت محاسبه رو بالا ببریم و همچنین حافطه مصرفی رو کاهش بدیم از DP استفاده می کنیم .

طبق گفته سوال بزرگترین self number ای که مورد سوال قرار می گیره از 10⁷ کمتره .

ما احتیاج داریم حاصل جمع هر عددی از 1 تا 10⁷ رو می خوایم .

برای اینکار از یه تکنیک ساده استفاده می کنیم .

برای همه عددهای کوچکتر از 10⁴ پیش محاسبه می کنیم .

برای محاسبه عددی مثل x کافیه 4 رقم اول اون رو جدا کنیم . حالا هر عددی تبدیل شده به دو قسمت که کوچکتر از 10⁴ هستند ، (d(n رو می تونیم تو (O(1 حساب کنیم .

حافطه این سوال خیلی پایینه برای همین نمی تونیم 10⁷ حافظه بگیریم .

برای حل این مشکل 2 راه ارائه میدیم .

راه اول

به اندازه n / 8 حافظه بگیریم و از هر بیت حافظه استفاده کنیم .

راه دوم

عدد ماکزیمم 7 رقمیه پس (d(n حداکثر 7 * 9 = 63 تا بیشتر از n میشه .

پس می تونیم یه لیست مثلا 1000 تایی بگیریم و به صورت دوری عددهارو روش مارک کنیم .