yukicoder no.16

問題文
http://ch.nicovideo.jp/programing/blomaga/ar604305

解法１
繰り返し二乗法を適用する。

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;

#define MOD (1000003)

ull pow(ull x, ull n) {
  if(n == 0) return 1;
  ull ret = pow(x*x%MOD, n/2);
  if(n&1) (ret *= x) %= MOD;
  return ret;
}

int main() {
  
  int x, N; cin >> x >> N;
  ull sum = 0;
  for(int i=0; i<N; i++) {
    ull a; cin >> a;
    (sum += pow(x, a)) %= MOD;
  }
  
  cout << sum << endl;
  
  return 0;
}

解法２（上のリンクの方の解答を参考、蟻本にも有る）
フェルマーの小定理

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;

#define MOD (1000003)

int fermat[MOD+1];

int main() {

  int x, N;
  cin >> x >> N;
  fermat[0] = 1;
  for(int i=0; i<MOD; i++) fermat[i+1] = (fermat[i]*x)%MOD;
  ull ans = 0;
  for(int i=0; i<N; i++) {
    int a; cin >> a;
    (ans += fermat[a%(MOD-1)]) %= MOD;
  }

  cout << ans << endl;
  
  return 0;
}