คำนวณค่า ฟังก์ชัน Y = (X^6 + X^2 + 9894845) % 981 ใน C++

โจทย์: หาค่า f(x) = (x^6 + x^2 + 9894845) % 971 สำหรับ x ที่กำหนด (หมายเหตุ: โจทย์เขียน 981 แต่โค้ดใช้ 971 ใช้ 971 ตามโค้ด)

ใช้ Modular Exponentiation (Binary Exponentiation) คำนวณ x^e mod m อย่างมีประสิทธิภาพ O(log e)

อัลกอริธึม power_mod(base, exp, mod)

1. base = base % mod
2. result = 1
3. วนลูปจน exp > 0:
   • ถ้า exp คี่: result = (result * base) % mod
   • base = (base * base) % mod
   • exp = exp / 2 (shift right)
4. คืน result

สูตรคำนวณสุดท้าย

result = (power_mod(n, 6, m) + power_mod(n, 2, m)) % m + 355) % m โดย m = 971

ตัวอย่างโค้ด 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;
}

อินพุต

84562

เอาต์พุท

450

ประยุกต์ใช้

Technique นี้ใช้ใน Cryptography, Competitive Programming, Hashing ที่ต้องคำนวณกำลังใหญ่ modulo