yukicoder 0016 累乗の加算

概要

$x$ と $a_1, \dots, a_n$ が与えられる. $x^{a_1} + \dots + x^{a_n} \bmod 1000003$ を求めよ.

制約

$1 \le x \le 100$, $0 \le a_i \le 10^8$.

解法

バイナリ法. $O(n \log a)$

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline ll powMod(ll b, ll e, ll m){
    ll res = 1;
    for(; e; e >>= 1, b = b * b % m) if(e&1) res = res * b % m;
    return res;
}

bool solve(){
    int x, n; cin >> x >> n;
    constexpr int mod = 1000 * 1000 + 3;
    ll res = 0;
    rep(_, n){
        int a; cin >> a;
        (res += powMod(x, a, mod)) %= mod;
    }
    cout << res << endl;
    return true;
}