結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0