ফ্যাক্টোরিয়াল মডুলো $p$#
কিছু ক্ষেত্রে কোনো মৌলিক সংখ্যা $p$ মডুলোতে জটিল সূত্র বিবেচনা করা প্রয়োজন, যেখানে লব এবং হর উভয়তেই ফ্যাক্টোরিয়াল থাকে, যেমন বাইনোমিয়াল কোএফিশিয়েন্টের সূত্রে দেখা যায়। আমরা সেই ক্ষেত্র বিবেচনা করি যখন $p$ তুলনামূলকভাবে ছোট। এই সমস্যাটি তখনই অর্থবহ যখন ফ্যাক্টোরিয়ালগুলো ভগ্নাংশের লব এবং হর উভয়তেই থাকে। অন্যথায় $p!$ এবং পরবর্তী পদগুলো শূন্যে নেমে যাবে। তবে ভগ্নাংশে $p$-এর গুণনীয়কগুলো বাতিল হতে পারে, এবং ফলস্বরূপ রাশিটি $p$ মডুলোতে অ-শূন্য হবে।
সুতরাং, আনুষ্ঠানিকভাবে কাজটি হলো: আপনি $n! \bmod p$ গণনা করতে চান, ফ্যাক্টোরিয়ালে প্রদর্শিত $p$-এর সকল গুণিতক গুণনীয়ক বিবেচনায় না নিয়ে। কল্পনা করুন আপনি $n!$-এর মৌলিক উৎপাদক বিভাজন লিখেছেন, সকল $p$ গুণনীয়ক সরিয়েছেন, এবং গুণফলটি $p$ মডুলোতে গণনা করেছেন। আমরা এই পরিবর্তিত ফ্যাক্টোরিয়ালকে $n!_{\%p}$ দ্বারা চিহ্নিত করব। উদাহরণস্বরূপ $7!_{\%p} \equiv 1 \cdot 2 \cdot \underbrace{1}_{3} \cdot 4 \cdot 5 \underbrace{2}_{6} \cdot 7 \equiv 2 \bmod 3$।
এই পরিবর্তিত ফ্যাক্টোরিয়াল কার্যকরভাবে গণনা করতে শেখা আমাদের বিভিন্ন কম্বিনেটোরিয়াল সূত্রের (উদাহরণস্বরূপ, বাইনোমিয়াল কোএফিশিয়েন্ট) মান দ্রুত গণনা করতে দেয়।
অ্যালগরিদম#
আসুন এই পরিবর্তিত ফ্যাক্টোরিয়ালটি সুস্পষ্টভাবে লিখি।
$$\begin{eqnarray} n!_{\%p} &=& 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}_{p} \cdot (p+1) \cdot (p+2) \cdot \ldots \cdot (2p-1) \cdot \underbrace{2}_{2p} \\\ & &\quad \cdot (2p+1) \cdot \ldots \cdot (p^2-1) \cdot \underbrace{1}_{p^2} \cdot (p^2 +1) \cdot \ldots \cdot n \pmod{p} \\\\ &=& 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}_{p} \cdot 1 \cdot 2 \cdot \ldots \cdot (p-1) \cdot \underbrace{2}_{2p} \cdot 1 \cdot 2 \\\ & &\quad \cdot \ldots \cdot (p-1) \cdot \underbrace{1}_{p^2} \cdot 1 \cdot 2 \cdot \ldots \cdot (n \bmod p) \pmod{p} \end{eqnarray}$$স্পষ্টভাবে দেখা যায় যে ফ্যাক্টোরিয়ালটি শেষটি ছাড়া একই দৈর্ঘ্যের কয়েকটি ব্লকে বিভক্ত।
$$\begin{eqnarray} n!_{\%p}&=& \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{1\text{st}} \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 2}_{2\text{nd}} \cdot \ldots \\\\ & & \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{p\text{th}} \cdot \ldots \cdot \quad \underbrace{1 \cdot 2 \cdot \cdot \ldots \cdot (n \bmod p)}_{\text{tail}} \pmod{p}. \end{eqnarray}$$ব্লকগুলোর মূল অংশ গণনা করা সহজ — এটি কেবল $(p-1)!\ \mathrm{mod}\ p$। আমরা এটি প্রোগ্রামগতভাবে গণনা করতে পারি অথবা উইলসনের উপপাদ্য প্রয়োগ করতে পারি যা বলে যে যেকোনো মৌলিক $p$-এর জন্য $(p-1)! \bmod p = -1$।
আমাদের ঠিক $\lfloor \frac{n}{p} \rfloor$ টি এই ধরনের ব্লক আছে, তাই আমাদের $-1$-কে $\lfloor \frac{n}{p} \rfloor$ ঘাতে উন্নীত করতে হবে। এটি বাইনারি এক্সপোনেনশিয়েশন ব্যবহার করে লগারিদমিক সময়ে করা যায়; তবে আপনি লক্ষ্য করতে পারেন যে ফলাফলটি $-1$ এবং $1$-এর মধ্যে পর্যায়ক্রমে পরিবর্তিত হয়, তাই আমাদের শুধু সূচকের সমতা দেখতে হবে এবং সমতা বিজোড় হলে $-1$ দিয়ে গুণ করতে হবে। এবং গুণের পরিবর্তে, আমরা বর্তমান ফলাফলকে $p$ থেকে বিয়োগও করতে পারি।
শেষ আংশিক ব্লকের মান আলাদাভাবে $O(p)$-এ গণনা করা যায়।
এটি শুধু প্রতিটি ব্লকের শেষ উপাদান রেখে যায়। যদি আমরা ইতিমধ্যে হ্যান্ডেল করা উপাদানগুলো আড়াল করি, আমরা নিম্নলিখিত প্যাটার্ন দেখতে পাই:
$$n!_{\%p} = \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 2} \cdot \ldots \cdot \underbrace{ \ldots \cdot (p-1)} \cdot \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 1} \cdot \underbrace{ \ldots \cdot 2} \cdots$$এটি আবার একটি পরিবর্তিত ফ্যাক্টোরিয়াল, শুধু অনেক ছোট মাত্রার। এটি $\lfloor n / p \rfloor !_{\%p}$।
সুতরাং, পরিবর্তিত ফ্যাক্টোরিয়াল $n\!_{\%p}$ গণনার সময় আমরা $O(p)$ অপারেশন সম্পাদন করেছি এবং $\lfloor n / p \rfloor !_{\%p}$ গণনা বাকি রয়েছে। আমাদের একটি রিকার্সিভ সূত্র আছে। রিকার্সনের গভীরতা $O(\log_p n)$, এবং তাই অ্যালগরিদমের সম্পূর্ণ অ্যাসিম্পটোটিক আচরণ $O(p \log_p n)$।
লক্ষ্য করুন, আপনি যদি ফ্যাক্টোরিয়ালগুলো $0!,~ 1!,~ 2!,~ \dots,~ (p-1)!$ $p$ মডুলোতে প্রিকম্পিউট করেন, তাহলে কমপ্লেক্সিটি কেবল $O(\log_p n)$ হবে।
ইমপ্লিমেন্টেশন#
আমাদের রিকার্সনের প্রয়োজন নেই কারণ এটি টেইল রিকার্সনের একটি ক্ষেত্র এবং তাই সহজেই ইটারেশন ব্যবহার করে ইমপ্লিমেন্ট করা যায়। নিম্নলিখিত ইমপ্লিমেন্টেশনে আমরা ফ্যাক্টোরিয়ালগুলো $0!,~ 1!,~ \dots,~ (p-1)!$ প্রিকম্পিউট করি, এবং তাই রানটাইম $O(p + \log_p n)$। যদি আপনাকে ফাংশনটি একাধিকবার কল করতে হয়, তাহলে আপনি প্রিকম্পিউটেশনটি ফাংশনের বাইরে করতে পারেন এবং $n!_{\%p}$-এর গণনা $O(\log_p n)$ সময়ে করতে পারেন।
int factmod(int n, int p) {
vector<int> f(p);
f[0] = 1;
for (int i = 1; i < p; i++)
f[i] = f[i-1] * i % p;
int res = 1;
while (n > 1) {
if ((n/p) % 2)
res = p - res;
res = res * f[n%p] % p;
n /= p;
}
return res;
}বিকল্পভাবে, আপনার কাছে সীমিত মেমোরি থাকলে এবং সকল ফ্যাক্টোরিয়াল সংরক্ষণ করা সম্ভব না হলে, আপনি শুধু প্রয়োজনীয় ফ্যাক্টোরিয়ালগুলো মনে রাখতে পারেন, সেগুলো সর্ট করতে পারেন, এবং তারপর সুস্পষ্টভাবে সংরক্ষণ না করে $0!,~ 1!,~ 2!,~ \dots,~ (p-1)!$ একটি লুপে গণনা করে একটি সুইপে সেগুলো গণনা করতে পারেন।
$p$-এর গুণিতকতা#
যদি আমরা একটি বাইনোমিয়াল কোএফিশিয়েন্ট $p$ মডুলোতে গণনা করতে চাই, তাহলে আমাদের অতিরিক্তভাবে $n$-এ $p$-এর গুণিতকতা প্রয়োজন, অর্থাৎ $n$-এর মৌলিক উৎপাদক বিভাজনে $p$ কতবার আসে, অথবা পরিবর্তিত ফ্যাক্টোরিয়ালের গণনার সময় আমরা কতবার $p$ মুছে ফেলেছি।
লেজান্দ্রের সূত্র আমাদের $O(\log_p n)$ সময়ে এটি গণনা করার একটি উপায় দেয়। সূত্রটি গুণিতকতা $\nu_p$ দেয়:
$$\nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$$সুতরাং আমরা পাই ইমপ্লিমেন্টেশন:
int multiplicity_factorial(int n, int p) {
int count = 0;
do {
n /= p;
count += n;
} while (n);
return count;
}এই সূত্রটি আগের অনুচ্ছেদগুলোতে আমরা যে ধারণাগুলো ব্যবহার করেছি সেই একই ধারণা ব্যবহার করে খুব সহজেই প্রমাণ করা যায়। $p$ গুণনীয়ক ধারণ করে না এমন সকল উপাদান সরিয়ে দিন। এতে $\lfloor n/p \rfloor$ টি উপাদান অবশিষ্ট থাকে। যদি আমরা তাদের প্রতিটি থেকে $p$ গুণনীয়কটি সরিয়ে দিই, আমরা গুণফল $1 \cdot 2 \cdots \lfloor n/p \rfloor = \lfloor n/p \rfloor !$ পাই, এবং আবার আমাদের একটি রিকার্সন আছে।