結果
問題 |
No.16 累乗の加算
|
ユーザー |
![]() |
提出日時 | 2015-06-13 10:27:27 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,685 bytes |
コンパイル時間 | 789 ms |
コンパイル使用メモリ | 90,456 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 04:56:05 |
合計ジャッジ時間 | 1,311 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <stack> #include <queue> #include <deque> #include <set> #include <map> #include <algorithm> // require sort next_permutation count __gcd reverse etc. #include <cstdlib> // require abs exit atof atoi #include <cstdio> // require scanf printf #include <functional> #include <numeric> // require accumulate #include <cmath> // require fabs #include <climits> #include <limits> #include <cfloat> #include <iomanip> // require setw #include <sstream> // require stringstream #include <cstring> // require memset #include <cctype> // require tolower, toupper #include <fstream> // require freopen #include <ctime> // require srand #define rep(i,n) for(int i=0;i<(n);i++) #define ALL(A) A.begin(), A.end() /* No.16 累乗の加算 累乗の計算 ループ版 ll mod_pow (ll x, ll n, ll mod ) { ll res = 1LL; while (n > 0 ){ if (n & 1 ) res = res*x % mod; x = x*x % mod; n >>=1; } // end while return res; } 再帰版 ll mod_pow (ll x, ll n, ll mod ) { if (n == 0 ) return 1LL; ll res = mod_pow (x*x % mod, n / 2, mod ); if (n & 1 ) res = res * x % mod; return res; } */ using namespace std; typedef long long ll; typedef pair<int, int> P; const ll MOD = (ll)1e6 + 3LL; ll mod_pow (ll x, ll n, ll mod ) { if (n == 0LL ) return 1LL; ll res = mod_pow (x*x % mod, n / 2LL, mod ); if (n & 1LL ) res = (res * x ) % mod; return res; } int main() { ios_base::sync_with_stdio(0); ll x, N; cin >> x >> N; vector<ll> a(N, 0LL ); rep (i, N ) cin >> a[i]; ll res = 0LL; rep (i, N ){ res = (res + mod_pow(x, a[i], MOD ) ) % MOD; } // end rep cout << (int)res << endl; return 0; }