結果
問題 | No.990 N×Mマス計算(Kの倍数) |
ユーザー |
![]() |
提出日時 | 2020-02-14 22:56:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 144 ms / 2,000 ms |
コード長 | 2,674 bytes |
コンパイル時間 | 1,114 ms |
コンパイル使用メモリ | 97,660 KB |
実行使用メモリ | 12,928 KB |
最終ジャッジ日時 | 2024-11-16 01:18:09 |
合計ジャッジ時間 | 2,551 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <map>#include <array>#include <cstdio>#include <cstring>#include <cmath>using namespace std;using ll = long long;int main() {ios::sync_with_stdio(false);cin.tie(0);int n, m, k;cin >> n >> m >> k;char op;cin >> op;ll r = 0;if (op == '+') {map<int, int> mp;for (int j = 0; j < m; j++) {int b;cin >> b;mp[b % k]++;}for (int i = 0; i < n; i++) {int a;cin >> a;int l = k - a % k;if (l == k) l = 0;r += mp[l];}} else {vector<pair<int, int>> p;int t = k;for (int i = 2; i * i <= t; i++) {int c = 0;while (t % i == 0) t /= i, c++;if (c > 0) p.push_back({ i, c });}if (t > 1) p.push_back({ t, 1 });int l = p.size();vector<array<int8_t, 9>> a(n), b(m);for (int j = 0; j < m; j++) {int t;cin >> t;for (int h = 0; h < l; h++) {int c = 0, d = p[h].first;while (c < p[h].second && t % d == 0) t /= d, c++;b[j][h] = c;}}for (int i = 0; i < n; i++) {int t;cin >> t;for (int h = 0; h < l; h++) {int c = 0, d = p[h].first;while (c < p[h].second && t % d == 0) t /= d, c++;a[i][h] = c;}}int s = 1;for (int h = 0; h < l; h++) {s *= p[h].second + 1;}vector<int> u(s);for (int i = 0; i < n; i++) {int t = 0, v = 1;for (int h = 0; h < l; h++) {t += a[i][h] * v;v *= p[h].second + 1;}u[t]++;}for (int h = 0, t = 1; h < l; h++) {int t2 = t * (p[h].second + 1);for (int t0 = 0; t0 < s; t0 += t2) {for (int t1 = 0; t1 < t; t1++) {for (int t4 = t2 - t; t4 > 0; t4 -= t) {int t3 = t0 + t1 + t4;u[t3 - t] += u[t3];}}}t = t2;}for (int j = 0; j < m; j++) {int t = 0, v = 1;for (int h = 0; h < l; h++) {t += (p[h].second - b[j][h]) * v;v *= p[h].second + 1;}r += u[t];}}cout << r << endl;return 0;}