結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1_sample1.txt AC 0 ms
3,236 KB
2_sample2.txt AC 0 ms
3,188 KB
3.txt AC 0 ms
3,284 KB
4.txt AC 0 ms
3,348 KB
5.txt AC 4 ms
3,192 KB
6.txt AC 4 ms
3,352 KB
7.txt AC 0 ms
3,108 KB
8.txt AC 0 ms
3,288 KB
9.txt AC 0 ms
3,280 KB
10.txt AC 4 ms
3,212 KB
11.txt AC 48 ms
4,056 KB
12.txt AC 60 ms
4,400 KB
13.txt AC 196 ms
4,880 KB
14.txt AC 36 ms
3,812 KB
15.txt AC 88 ms
4,444 KB
16.txt AC 48 ms
4,064 KB
17.txt AC 60 ms
4,188 KB
18.txt AC 40 ms
3,716 KB
19.txt AC 200 ms
4,960 KB
20.txt AC 72 ms
4,220 KB
テストケース一括ダウンロード

ソースコード

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<ll, 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