結果

問題 No.990 N×Mマス計算(Kの倍数)
ユーザー cotton_fn_
提出日時 2020-02-15 02:10:17
言語 C++17(1z)
(gcc 9.2.0)
結果
AC  
実行時間 196 ms
コード長 1,442 Byte
コンパイル時間 1,056 ms
使用メモリ 10,332 KB
最終ジャッジ日時 2020-02-15 02:10:20

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1_sample1.txt AC 0 ms
3,196 KB
2_sample2.txt AC 0 ms
3,152 KB
3.txt AC 0 ms
3,064 KB
4.txt AC 0 ms
3,284 KB
5.txt AC 4 ms
3,212 KB
6.txt AC 0 ms
3,180 KB
7.txt AC 0 ms
3,216 KB
8.txt AC 0 ms
3,160 KB
9.txt AC 0 ms
3,220 KB
10.txt AC 0 ms
3,240 KB
11.txt AC 68 ms
8,308 KB
12.txt AC 56 ms
3,824 KB
13.txt AC 192 ms
4,560 KB
14.txt AC 36 ms
3,468 KB
15.txt AC 72 ms
4,044 KB
16.txt AC 44 ms
3,568 KB
17.txt AC 88 ms
10,332 KB
18.txt AC 36 ms
3,460 KB
19.txt AC 196 ms
4,628 KB
20.txt AC 64 ms
3,756 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <complex>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
#include <iterator>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

i64 gcd(i64 x, i64 y) {
    while (y > 0) {
        x %= y;
        swap(x, y);
    }
    return x;
}

int main() {
    i64 n, m, k;
    char op;
    cin >> n >> m >> k >> op;
    vector<i64> a(n), b(m);
    for (int i = 0; i < m; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) cin >> a[i];

    i64 ans = 0;
    if (op == '+') {
        map<i64, i64> ma, mb;
        for (i64 x : a) ma[x % k]++;
        for (i64 x : b) mb[x % k]++;
        for (auto p : ma) {
            i64 x, c;
            tie(x, c) = p;
            ans += c * mb[(k - x) % k];
        }
    } else {
        map<i64, i64> ma, mb;
        for (i64 x : a) ma[gcd(x, k)]++;
        for (i64 x : b) mb[gcd(x, k)]++;
        for (auto p : ma) {
            i64 x, c;
            tie(x, c) = p;
            for (auto p : mb) {
                i64 y, d;
                tie(y, d) = p;
                if (x * y % k == 0) {
                    ans += c * d;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}
0