結果
問題 | No.16 累乗の加算 |
ユーザー |
![]() |
提出日時 | 2019-03-01 00:55:53 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,015 bytes |
コンパイル時間 | 1,309 ms |
コンパイル使用メモリ | 165,032 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-23 11:55:45 |
合計ジャッジ時間 | 1,909 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long LL;const LL MOD = 1e6 + 3;// x の A乗 を MOD で割った余りを計算.// @param x: 基準とする数.// @param A: べき乗.// @return ans: 余り.LL mod(LL x, LL A){// 1. N を 2で割っていく.map<LL, LL> m;while(A){LL q = A / 2;LL r = A % 2;m[q] = r;A /= 2;}// for(auto &p : m) cout << p.first << " " << p.second << endl;// 2. 1. の 結果から, 余りを逆算.LL ans = 1;for(auto &p : m){if(p.first != 0) ans *= ans, ans %= MOD;if(p.second == 1) ans *= x, ans %= MOD;}return ans;}int main() {// 1. 入力情報取得.LL x, N;cin >> x >> N;// 2. 各べき乗の項の合計は?LL ans = 0;for(LL i = 0; i < N; i++){LL a;cin >> a;ans += mod(x, a);ans %= MOD;}// 3. 後処理.cout << ans << endl;return 0;}