結果
問題 | No.2709 1975 Powers |
ユーザー |
|
提出日時 | 2024-03-31 01:29:08 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 1,341 bytes |
コンパイル時間 | 846 ms |
コンパイル使用メモリ | 131,428 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-30 17:47:33 |
合計ジャッジ時間 | 4,072 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include <algorithm> #include <cassert> #include <iostream> #include <vector> using namespace std; long long pow_mod(long long x, long long n, long long mod) { long long ret = 1; while (n > 0) { if (n & 1) { ret *= x; ret %= mod; } x *= x; x %= mod; n >>= 1; } return ret; } int main() { int n, p, q; cin >> n >> p >> q; assert(4 <= n && n <= 200); assert(2 <= q && q < p && p <= 100000); vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } for (int i = 0; i < n; ++i) { assert(1 <= a[i] && a[i] <= 2000000); } sort(a.begin(), a.end()); vector<int> m10(n), m9(n), m7(n), m5(n); for (int i = 0; i < n; ++i) { m10[i] = pow_mod(10, a[i], p); m9[i] = pow_mod(9, a[i], p); m7[i] = pow_mod(7, a[i], p); m5[i] = pow_mod(5, a[i], p); } int ans = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { for (int l = k + 1; l < n; ++l) { long long sum = m10[i] + m9[j] + m7[k] + m5[l]; if (sum % p == q) { ans += 1; } } } } } cout << ans << endl; return 0; }