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;
}