[蓝桥杯2020年第十一届省赛真题-八次求和] 快速幂

参考代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 123456789;

ll quick_pow(ll a, ll b) {

    ll ans = 1;

    while (b) {

        if (b & 1) {

            ans = ans * a % N;

        }

        a = a * a % N;

        b >>= 1;

    }

    return ans;

}

int main(void) {

    int n;

    ll cnt = 1;

    scanf("%d", &n);

    for (int i = 2; i <= n; i++) {

        cnt += quick_pow(i, 8);

    }

    printf("%lld\n", cnt % N);

    return 0;

}