結果
問題 | No.990 N×Mマス計算(Kの倍数) |
ユーザー | heno239 |
提出日時 | 2020-02-15 03:38:21 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 1,833 bytes |
コンパイル時間 | 1,345 ms |
コンパイル使用メモリ | 125,988 KB |
実行使用メモリ | 14,464 KB |
最終ジャッジ日時 | 2024-04-27 20:43:52 |
合計ジャッジ時間 | 2,314 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 29 ms
7,040 KB |
testcase_11 | AC | 15 ms
6,944 KB |
testcase_12 | AC | 83 ms
6,940 KB |
testcase_13 | AC | 11 ms
6,944 KB |
testcase_14 | AC | 26 ms
6,940 KB |
testcase_15 | AC | 13 ms
6,940 KB |
testcase_16 | AC | 38 ms
7,936 KB |
testcase_17 | AC | 12 ms
6,944 KB |
testcase_18 | AC | 81 ms
6,944 KB |
testcase_19 | AC | 47 ms
6,940 KB |
testcase_20 | AC | 97 ms
14,464 KB |
ソースコード
#include<iostream> #include<string> #include<cstdio> #include<vector> #include<cmath> #include<algorithm> #include<functional> #include<iomanip> #include<queue> #include<ciso646> #include<utility> #include<map> #include<set> #include<bitset> #include<stack> #include<cassert> #include<random> #include<unordered_map> #include<numeric> using namespace std; using ll = long long; const ll mod = 1000000007; const ll INF = (1e+18) + 7; #define rep(i,n) for(int i=0;i<n;i++) #define Rep(i,sta,n) for(int i=sta;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define all(x) (x).begin(),(x).end() #define stop char nyaa;cin>>nyaa; using P = pair<int, int>; using LP = pair<ll, ll>; int h, w; ll x; ll a[1 << 17], b[1 << 17]; void solvep() { map<int, int> mp; rep(j, w) { mp[b[j] % x]++; } ll ans = 0; rep(i, h) { int rest = x - (a[i]) % x; if (rest == x)rest = 0; ans += mp[rest]; } cout << ans << endl; } ll gcd(ll a, ll b) { if (a < b)swap(a, b); while (b) { ll r = a % b; a = b; b = r; } return a; } void solvem() { vector<ll> ds; int k = sqrt(x + 0.1); for (int i = 1; i <= k; i++) { if (x%i == 0) { ds.push_back(i); ds.push_back(x / i); } } sort(all(ds)); ds.erase(unique(all(ds)), ds.end()); map<int, int> mp; rep(i, ds.size())mp[ds[i]] = i; vector<ll> ch(ds.size()), cw(ds.size()); rep(i, h) { ch[mp[gcd(a[i], x)]]++; } rep(j, w) { cw[mp[gcd(b[j], x)]]++; } ll ans = 0; rep(i, ch.size())rep(j, cw.size()) { if (ds[i] * ds[j] % x == 0) { ans += ch[i] * cw[j]; } } cout << ans << endl; } void solve() { cin >> h >> w>>x; char c; cin >> c; rep(j, w)cin >> b[j]; rep(i, h)cin >> a[i]; if (c == '+') { solvep(); } else { solvem(); } } signed main() { cin.tie(0); ios::sync_with_stdio(false); //int t; cin >> t;rep(i,t) solve(); solve(); stop return 0; }