ফ্যাক্টোরিয়াল ভাজকের ঘাত নির্ণয়#

আপনাকে দুটি সংখ্যা $n$ ও $k$ দেওয়া আছে। এমন সর্ববৃহৎ পূর্ণসংখ্যা $x$ খুঁজুন যেন $k^x$ $n!$-কে ভাগ করে।

মৌলিক $k$#

প্রথমে মৌলিক $k$-এর ক্ষেত্রটি বিবেচনা করি। ফ্যাক্টোরিয়ালের সুস্পষ্ট রাশি

লক্ষ্য করুন যে গুণফলের প্রতি $k$-তম উপাদান $k$ দ্বারা বিভাজ্য, অর্থাৎ উত্তরে $+1$ যোগ করে; এই ধরনের উপাদানের সংখ্যা $\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor$।

এরপর, প্রতি $k^2$-তম উপাদান $k^2$ দ্বারা বিভাজ্য, অর্থাৎ উত্তরে আরেকটি $+1$ যোগ করে (আগের অনুচ্ছেদে $k$-এর প্রথম ঘাত ইতিমধ্যে গণনা করা হয়েছে)। এই ধরনের উপাদানের সংখ্যা $\Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor$।

এবং এভাবে চলতে থাকে, প্রতি $i$-এর জন্য প্রতিটি $k^i$-তম উপাদান উত্তরে আরেকটি $+1$ যোগ করে, এবং এরকম $\Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor$ টি উপাদান আছে।

চূড়ান্ত উত্তর হলো

এই ফলাফলটি লেজান্দ্রের সূত্র নামেও পরিচিত। যোগফলটি অবশ্যই সসীম, কারণ আনুমানিকভাবে প্রথম $\log_k n$ টি উপাদানই শূন্য নয়। সুতরাং, এই অ্যালগরিদমের রানটাইম $O(\log_k n)$।

ইমপ্লিমেন্টেশন#

int fact_pow (int n, int k) {
	int res = 0;
	while (n) {
		n /= k;
		res += n;
	}
	return res;
}

যৌগিক $k$#

একই ধারণা সরাসরি প্রয়োগ করা যায় না। পরিবর্তে আমরা $k$-কে ফ্যাক্টরাইজ করতে পারি, এটিকে $k = k_1^{p_1} \cdot \ldots \cdot k_m^{p_m}$ হিসেবে উপস্থাপন করে। প্রতিটি $k_i$-এর জন্য, উপরে বর্ণিত অ্যালগরিদম ব্যবহার করে $n!$-এ এটি কতবার উপস্থিত তা খুঁজে বের করি - একে $a_i$ বলি। যৌগিক $k$-এর জন্য উত্তর হবে