結果

問題 No.990 N×Mマス計算（Kの倍数）
コンテスト
ユーザー merom686
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0