سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 10:03:02 -0600 امیر شکریآمار پرسش:
- پرسیده شده: 2015-09-03 09:35:29 -0600
- مشاهده شده: 835 بار
- بروز شده: 2015-09-03 19:46:05 -0600
پرسش‌های مشابه:
نظریه اعداد لازم برای المپیاد کامپیوتری ها
فلسفه ی وجود و یا عدم وجود جفت اعداد مسخره
محاسبه ${n \choose k}$ به پیمانه M
وبسایت مسابقه‌های برنامه نویسی
یافتن کوتاه ترین دور در گراف ساده
کد مساله هشت وزیر با استفاده از الگوریتم ژنتیک
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
BWC Round #1 - ک.م.م - ک.م.م اعداد ۱ تا n را بیابید.
عمه گوهر عاشق ک.م.م اعداد شده است، ک.م.م دو عدد طبیعی $x$ و $y$ برابر کوچک ترین عددی است که مضرب مشترکی از $x$ و $y$ باشد، به‌طورمثال ک.م.م ۱۰ و ۱۴ برابر با ۷۰ است.
حال او به دنبال ک.م.م اعداد $1,2,3,4, ..., n$ است، اگر ک.م.م این اعداد را $A(n)$ بنامیم.
الف) مقدار باقی‌مانده‌ی $A(20)^3$ بر تقسیم در $\Delta$ را حساب کنید.
ب) مقدار باقی‌مانده‌ی $A(۱۰۰۰)^3$ بر تقسیم در $\Delta$ را حساب کنید.
اگر $B(n)$ را برابر باقی‌مانده‌ی $A(n)$ بر تقسیم بر $10^9+7$ بنامیم.
ج)مقدار باقی‌مانده‌ی $B(1000000)^3$ در تقسیم بر $\Delta$ را حساب کنید.
د) مقدار باقی‌مانده‌ی $B(1) + B(2) + B(3) + ... + B(1000000)$ در تقسیم بر $\Delta$ را حساب کنید.
لینک سوالات:
2015-09-03 09:35:29 -0600
توفیقی 1621 ● 17 ● 21 ● 42
نظرات
2 پاسخ
جواب خودم:
راه حل این سوال به وسیله‌ی غربال اراتستن با $O(n lgn)$ بود، بدین صورت که اگه $f(i)$ رو برابر مقداری که عدد i در ضرب ما تاثیر داره بدونیم،
پاسخ مسئله برابر با $f(1)×f(2)×…×f(n)$ بود،
مثلا: $$ f(1)=1,f(2)=2,f(3)=3,f(4)=2,f(5)=5,f(6)=1,…. $$ خوب حالا اگه عنصر i ام به مقدار $f(i)$ در ک.م.م تاثیر بذاره، تاثیر گذاری عدد $i×k (k∈Z,k≥2)$ تقسیم بر $f(i)$ میشه، اثباتش هم بدیهی هست دیگه، حالا از همین استفاده می‌کنیم، در ابتدا مقدار $f(i)=i$ در نظر بگیرید، بعد به ازای هر $i (1≤i≤n)$ مقدار $A$ رو در $f(i)$ ضرب کنید و $f(i×k)$ رو تقسیم بر $f(i)$ کنید، قسمت الف و ب و ج با استفاده از این ایده حل میشه، برای قسمت د، مقدار $Ans=0$ رو در ابتدای کدتون تعریف کنید و در هر مرحله مقدار Ans رو به اضافه‌ی A کنید.
کد A2:
http://paste.white-crow.ir/view/306/2y10mQiuaN19LOX
کد A3:
http://paste.white-crow.ir/view/307/2y10gNCXsKUggDp
کد A4:
http://paste.white-crow.ir/view/305/2y10fmM76Wezs09
PDF جواب: http://bayanbox.ir/download/2319617824914718503/BWC-1-javab.pdf
2015-09-03 19:46:05 -0600
توفیقی 1621 ● 17 ● 21 ● 42
سلام،جواب: ابتدا میاییم تمام اعداد اول رو تا n به دست میاوریم(با اوی n log logn) حال ک.م.م میشه حاصل ضرب بزرگترین توان اعداد اول.برای قسمت د هم میایم dp میزنیم.
2015-09-03 15:19:18 -0600
حسن رستمی پور 98 ● 2 ● 3 ● 9
نظرات
@حسن رستمی پور چرا log log n؟ مگه غربال نمیزنی؟ غربال $O(n lg n)$ محسوب میشه.
2015-09-03 19:38:47 -0600 توفیقی@توفیقی روش غربال رو یکم optimize می کنیم:https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
2015-09-04 00:27:25 -0600 حسن رستمی پور