結果
問題 | No.990 N×Mマス計算(Kの倍数) |
ユーザー |
|
提出日時 | 2020-02-14 22:44:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,596 bytes |
コンパイル時間 | 2,972 ms |
コンパイル使用メモリ | 205,676 KB |
最終ジャッジ日時 | 2025-01-09 00:24:42 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 RE * 1 |
ソースコード
#include <bits/stdc++.h> // clang-format offusing namespace std;using Int = int;#define REP2(i, n) for (Int i = 0, max_i = (n); i < max_i; i++)#define REP3(i, a, b) for (Int i = (a), max_i = (b); i < max_i; i++)#define OVERLOAD2(_1, _2, _3, name, ...) name#define REP(...) OVERLOAD2(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)struct SetupIO { SetupIO() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(13); } } setup_io;#ifndef _MY_DEBUG#define dump(...)#endif // clang-format on/*** author: knshnb* created: Fri Feb 14 21:57:55 JST 2020**/signed main() {Int n, m, K;cin >> n >> m >> K;char op;cin >> op;vector<Int> b(m);REP(j, m) cin >> b[j];vector<Int> a(n);REP(i, n) cin >> a[i];sort(a.begin(), a.end());sort(b.begin(), b.end());long long ans = 0;if (op == '+') {vector<Int> num(K);REP(j, m) {num[b[j] % K]++;}REP(i, n) {Int tmp = (K - a[i] % K) % K;ans += num[tmp];}} else {unordered_map<Int, Int> c;REP(j, m) {c[__gcd(b[j], K)]++;}unordered_map<Int, Int> mp;REP(i, n) {Int x = K / __gcd(a[i], K);if (mp.count(x)) {ans += mp.at(x);} else {Int cnt = 0;for (auto& p : c) {cnt += p.second * (p.first % x == 0);}ans += (mp[x] = cnt);}}}cout << ans << endl;}