結果

問題 No.990 N×Mマス計算(Kの倍数)
ユーザー heno_code
提出日時 2020-02-15 03:38:21
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 92 ms
コード長 1,833 Byte
コンパイル時間 1,136 ms
使用メモリ 7,632 KB
最終ジャッジ日時 2020-02-15 03:38:24

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1_sample1.txt AC 4 ms
3,172 KB
2_sample2.txt AC 0 ms
3,316 KB
3.txt AC 0 ms
3,172 KB
4.txt AC 4 ms
3,184 KB
5.txt AC 0 ms
3,320 KB
6.txt AC 0 ms
3,168 KB
7.txt AC 4 ms
3,292 KB
8.txt AC 0 ms
3,300 KB
9.txt AC 4 ms
3,260 KB
10.txt AC 0 ms
3,168 KB
11.txt AC 36 ms
6,848 KB
12.txt AC 16 ms
4,356 KB
13.txt AC 92 ms
4,900 KB
14.txt AC 12 ms
3,992 KB
15.txt AC 28 ms
4,556 KB
16.txt AC 16 ms
4,108 KB
17.txt AC 48 ms
7,632 KB
18.txt AC 16 ms
3,916 KB
19.txt AC 92 ms
4,968 KB
20.txt AC 52 ms
4,280 KB
テストケース一括ダウンロード

ソースコード

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