C++-এ ফাংশন Y = (X^6 + X^2 + 9894845) % 981 এর মান বের করা

সমস্যা

ফাংশন: f(x) = (x^6 + x^2 + 9894845) % 971। বড় x-এর জন্য সরাসরি হিসাব করলে ওভারফ্লো হতে পারে। মডুলার এক্সপোনেনশিয়েশন ব্যবহার করতে হবে।

অ্যালগরিদম: Modular Exponentiation

1. power_mod(base, exponent, modulus) ফাংশন লিখুন।
2. base = base % modulus।
3. result = 1।
4. while (exponent > 0):
   • যদি এক্সপোনেন্ট বিষম হয়: result = (result * base) % modulus।
   • base = (base * base) % modulus।
   • exponent >>= 1 (২ দিয়ে ভাগ)।
5. ফাইনাল ফলাফল: ((power_mod(n,6,m) + power_mod(n,2,m)) % m + 355) % m। (নোট: 9894845 % 971 = 355)

C++ কোড

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

lli power_mod(lli base, lli exponent, lli modulus) {
    base %= modulus;
    lli result = 1;
    while (exponent > 0) {
        if (exponent & 1)
            result = (result * base) % modulus;
        base = (base * base) % modulus;
        exponent >>= 1;
    }
    return result;
}

int main() {
    lli n = 654654, m = 971;
    cout << ((power_mod(n, 6, m) + power_mod(n, 2, m)) % m + 355) % m;
}

ইনপুট/আউটপুট

Input: 84562
Output: 450