Yukicoder016 累乗の加算

問題概要

$x,N,$数列${a}$が与えられる。 $x^{a1}+x^{a2}+⋯+x^{aN}$を$mod1,000,003$で求めよ。

$N\leqq10^2$、$x\leqq10^2$、$a[i]\leqq10^8$

yukicoder016

解法

繰り返し2乗法をやればよい

計算量:$O(Nlog(mod))$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    long long  powmod(long long  x, long long  n, long long  mod) {
        long long  res = 1;
        while (n > 0) {
            if (n & 1) {
                res = (res*x) % mod;
            }
            x = (x*x) % mod;
            n >>= 1;
        }
        return res;
    }
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        LL x;
        cin >> x >> N;
        const LL mod = 1000003;
    
        FOR(i, 0, N) {
            LL a; cin >> a;
            ans += powmod(x, a, mod);
            ans %= mod;
        }
        cout << ans << "\n";
    
        return 0;
    }