Tính giá trị hàm Y = (X^6 + X^2 + 9894845) % 981 trong C++

Bài toán tính f(x) = (x^6 + x^2 + 9894845) % 971 (lưu ý: đề bài viết 981 nhưng code dùng 971, ta dùng 971 theo code). Sử dụng modular exponentiation để tránh tràn số.

Thuật toán lũy thừa modulo (Binary Exponentiation)

long long power_mod(long long base, long long exp, long long mod) {
    base %= mod;
    long long res = 1;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

Chương trình hoàn chỉnh

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

lli power_mod(lli base, lli exp, lli mod) {
    base %= mod;
    lli res = 1;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    lli n = 654654, m = 971;
    // f(n) = (n^6 + n^2 + 9894845) % m
    // 9894845 % 971 = 355
    lli ans = (power_mod(n, 6, m) + power_mod(n, 2, m) + 355) % m;
    cout << ans;
    return 0;
}

Kết quả với input 84562

450

Độ phức tạp: O(log exponent) cho mỗi lần gọi power_mod.