結果

問題 No.990 N×Mマス計算(Kの倍数)
ユーザー chocorusk
提出日時 2020-02-15 04:44:34
言語 C++14
(gcc 9.2.0)
結果
WA   .
実行時間 -
コード長 1,281 Byte
コンパイル時間 1,012 ms
使用メモリ 4,884 KB
最終ジャッジ日時 2020-02-15 04:44:38

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1_sample1.txt AC 4 ms
3,200 KB
2_sample2.txt AC 0 ms
3,252 KB
3.txt AC 4 ms
3,172 KB
4.txt AC 0 ms
3,228 KB
5.txt AC 4 ms
3,156 KB
6.txt AC 0 ms
3,236 KB
7.txt AC 0 ms
3,152 KB
8.txt AC 4 ms
3,152 KB
9.txt AC 0 ms
3,312 KB
10.txt AC 0 ms
3,308 KB
11.txt AC 48 ms
4,020 KB
12.txt AC 60 ms
4,364 KB
13.txt WA -
14.txt AC 40 ms
3,840 KB
15.txt AC 88 ms
4,484 KB
16.txt AC 48 ms
3,896 KB
17.txt AC 60 ms
4,124 KB
18.txt AC 40 ms
3,792 KB
19.txt WA -
20.txt WA -
テストケース一括ダウンロード

ソースコード

diff #
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
ll gcd(ll a, ll b){
	if(b==0) return a;
	return gcd(b, a%b);
}
int main()
{
	int n, m;ll k;
	cin>>n>>m>>k;
	char op; cin>>op;
	ll a[100001], b[100001];
	for(int i=0; i<m; i++) cin>>b[i], b[i]%=k;
	for(int i=0; i<n; i++){
		cin>>a[i];a[i]%=k;
	}
	if(op=='+'){
		ll ans=0;
		sort(b, b+m);
		for(int i=0; i<n; i++){
			int j=lower_bound(b, b+m, (k-a[i])%k)-b;
			int l=upper_bound(b, b+m, (k-a[i])%k)-b;
			ans+=l-j;
		}
		cout<<ans<<endl;
		return 0;
	}
	map<int, ll> mp1, mp2;
	for(int i=0; i<n; i++){
		a[i]=gcd(a[i], k);
		mp1[a[i]]++;
	}
	for(int i=0; i<m; i++){
		b[i]=gcd(b[i], k);
		mp2[b[i]]++;
	}
	ll ans=0;
	for(auto p:mp1){
		for(auto q:mp2){
			if(p.first*q.first%k==0) ans+=p.second*q.second;
		}
	}
	cout<<ans<<endl;
	return 0;
}
0