結果

問題 No.990 N×Mマス計算（Kの倍数）
ユーザー tomoron13tomoron13
提出日時 2020-06-03 00:11:58
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 176 ms / 2,000 ms
コード長 9,121 bytes
コンパイル時間 1,414 ms
コンパイル使用メモリ 118,364 KB
実行使用メモリ 17,536 KB
最終ジャッジ日時 2024-11-24 19:55:22
合計ジャッジ時間 3,579 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 1 ms
6,820 KB
testcase_09 AC 1 ms
6,820 KB
testcase_10 AC 54 ms
7,936 KB
testcase_11 AC 40 ms
6,820 KB
testcase_12 AC 155 ms
6,816 KB
testcase_13 AC 25 ms
6,820 KB
testcase_14 AC 57 ms
6,816 KB
testcase_15 AC 34 ms
6,816 KB
testcase_16 AC 68 ms
8,960 KB
testcase_17 AC 26 ms
6,820 KB
testcase_18 AC 149 ms
6,816 KB
testcase_19 AC 50 ms
6,820 KB
testcase_20 AC 176 ms
17,536 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <cmath>
#include <deque>
#include <iostream>
#include <limits.h>
#include<functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <stack>
#include <deque>
#include <tuple>
#include <float.h>
#include<time.h>

#define LL long long
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define mp make_pair
#define mt make_tuple
#define pq priority_queue<LL>
#define pqg priority_queue<LL,vector<LL>,greater<LL>>
#define pb push_back
#define vecLL vector<LL>
#define vecpii vector<pii>
#define vecpLL vector<pLL>
#define vecbL vector<bool>
#define endl "\n"
#define REP(e,v) for(auto e:v)
#define rep(i, a, n) for(LL i = a; i < n;i++)
#define Arep(i, a, n) for(i = a; i < n;i++)
#define MOD 1000000007
#define INF LLONG_MAX/2
#define DINF DBL_MAX/2
using namespace std;


/*↓マイライブラリ↓*/

//clock_t start = clock();
//
//clock_t end = clock();
//
//const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
//printf("time %lf[ms]\n", time);

LL linp(){
	LL x;
	scanf("%lld",&x);
	return x;
}

map<LL,LL> factalization(LL N){
	map<LL,LL> fac;
	LL oriN = N;
	LL div = 1;
	for(LL i = 2;i*i <= N;++i){
		while(N%i == 0){
			fac[i]++;
			div *= i;
			N /= i;
		}
	}
	if(oriN/div != 1){
		fac[oriN/div]++;
	}
	return fac;
}

vecLL bit(LL i,LL N){
	vecLL biti(N);

	rep(x,0,N){
		biti[N - 1 - x] = (i >> x) & 1;
	}

	return biti;
}

void swap(LL &a, LL &b){
	LL t = a;
	a = b;
	b = t;

	return ;
}

LL mod(LL i){
	LL mi = i % MOD;

	if(mi < 0)
		mi += MOD;

	return mi;
}

LL digit(LL x,LL n){
	LL count = 1;

	while(x >= n){
		x = x/n;
		count++;
	}
	return count;
}

LL gcd(LL i,LL j){
	if(j != 0)
		return gcd(j, i % j);
	else
		return i;
}

pLL extgcd(LL a,LL b){//ax+by = 1の解

	pLL ans;

	if(b != 0){
		pLL next = extgcd(b,a%b);
		ans.first = next.second;
		ans.second = next.first-(a/b)*next.second;
	}
	else{
		ans = pLL(1,0);
	}

	return ans;
}


LL division(LL a, LL b,LL m){

	return mod(mod(a) * mod(extgcd(b,m).first));
}

LL numperm_mod(LL x,LL y){
	LL res = 1;
	for(LL i = x; i >= y; i--){
		res = mod(res * mod(i));
	}
	return mod(res);
}

LL numperm(LL x,LL y){
	LL res = 1;
	for(LL i = x; i >= y; i--){
		res *= i;
	}
	return res;
}


LL pow_mod(LL x,LL y){

	x = mod(x);

	if(y == 1){
		return mod(x);
	}
	LL res = mod(pow_mod(mod(x*x),y/2));
	if(y % 2 == 0){
		return res;
	}
	else{
		return mod(x*res);
	}
}

LL pow(LL x,LL y){

	if(y == 1){
		return x;
	}
	if(y % 2 == 0){
		return pow(x*x,y/2);
	}
	else{
		return x*pow(x*x,y/2);
	}
}


bool isPrime(LL X){
	rep(i,2,(LL)(sqrt(X)+1)){
		if(X % i == 0){
			return false;
		}
	}
	return true;
}

 vecLL Eratosthenes(LL n){//素数のベクトルを返す

	 bool isPrime[n];
	 fill(isPrime,isPrime+n,true);

	 isPrime[0] = isPrime[1] = false;
	 rep(i,2,sqrt(n)+1){
		 if(isPrime[i]){
			 for(LL j = 2*i ;j <= n ; j += i){
				 isPrime[j] = false;
			 }
		 }
	 }

	 vecLL P;

	 rep(i,2,n+1){
		 if(isPrime[i]){
			 P.push_back(i);
		 }
	 }

	 return P;
}

 struct edge {//枝
	LL to,cost;
	double dcost;//コストが整数でない場合に使う
} ;


struct vertex{//頂点(枝付き)
	LL key;
	double dkey;//キーが整数でない場合に使う
	vector<edge> edges;//頂点から伸びる枝
};

class Graph{

public:

	LL V;//頂点数
	vertex* vertices;//グラフ


	Graph(LL v){//頂点数を指定してグラフの初期化
		V = v;//頂点数
		vertices = new vertex[V];//頂点集合

		rep(i,0,V){
			vertices[i].key = -1;//キー初期値は-1
			vertices[i].dkey = -1;//キー初期値は-1
		}

	}

	void setDE(LL i,LL j,LL cos){//i→jにコストcosの有向枝を加える

			edge e;
			e.to= j;
			e.cost = cos;

			vertices[i].edges.push_back(e);

			return;
	}

	void setDE(LL i,LL j,double dcos){//i→jにコストcosの有向枝を加える

				edge e;
				e.to= j;
				e.dcost = dcos;

				vertices[i].edges.push_back(e);

				return;
	}

	void setUDE(LL i,LL j,LL cos){//(i,j)にコストcosの無向枝を加える

		edge ei,ej;
		ei.to = j;
		ej.to = i;
		ei.cost = ej.cost = cos;

		vertices[i].edges.push_back(ei);
		vertices[j].edges.push_back(ej);

		return;
	}

	void setUDE(LL i,LL j,double dcos){//(i,j)にコストcosの無向枝を加える

		edge ei,ej;
		ei.to = j;
		ej.to = i;
		ei.dcost = ej.dcost = dcos;

		vertices[i].edges.push_back(ei);
		vertices[j].edges.push_back(ej);

		return;
	}

	void setKey(LL i,LL newKey){//キー変更
		vertices[i].key = newKey;
	}

	void setKey(LL i,double newKey){//キー変更
		vertices[i].key = newKey;
	}

	 edge getEdge(LL i,LL j){

		 rep(a,0,vertices[i].edges.size()){
			 if(vertices[i].edges[a].to == j){
				 return vertices[i].edges[a];
			 }
		 }

		 return (edge){j,INF,DINF};//なければ,コストINFの枝を返す
	}

	void bellman_ford(LL s,LL b[]){
		 fill(b,b+V,INF);

		 b[s] = 0;


		 while(true){

			 bool update = false;
			 rep(i,0,V){
				rep(j,0,vertices[i].edges.size()){
					edge e = vertices[i].edges[j];

					if(b[e.to] > b[i] + e.cost){
						b[e.to] = b[i] + e.cost;
						update = true;
					}

				}
			}
			if(!update)
				break;
		 }

		 return;
	}

	void dijkstra(LL s, LL d[]) {//ダイクストラ(始点を入力とし、各点への最小距離を返す)

	    priority_queue<pLL, vector<pLL>, greater<pLL> > que;

	    fill(d,d+V,INF);
	    d[s] = 0;
	    que.push(pLL(0, s));

	    while (!que.empty()) {
	        pLL p = que.top();
	        que.pop();
	        LL v = p.second;
	        if (d[v] < p.first) continue;

	        rep(i,0, vertices[v].edges.size()) {
	            edge e = vertices[v].edges[i];
	            if (d[e.to] > d[v] + e.cost) {
	                d[e.to] = d[v] + e.cost;
	                que.push(pLL(d[e.to], e.to));
	            }
	        }
	    }

	    return;

	}

	void warshall_floyd(LL **w){

		rep(i,0,V){
					rep(j,0,V){
						w[i][j] = INF;
					}
		}
		rep(i,0,V){
			rep(j,0,vertices[i].edges.size()){
				w[i][vertices[i].edges[j].to] = vertices[i].edges[j].cost;
			}
		}

		rep(i,0,V){
				w[i][i] = 0;
		}

		rep(i,0,V){
			rep(j,0,V){
				rep(k,0,V){
					w[i][j] = min(w[i][j],w[i][k]+w[k][j]);
				}
			}
		}

	}



};

class UF
{
public:
	LL N;
	LL* par;
	LL*  rank;

	UF(LL n){
		 N = n;

		 par = new LL[N];
		 rank = new LL[N];

		 rep(i,0,N){
			 par[i] = i;
			 rank[i] = i;
		 }

		 return;

	}

	LL root(LL x){
		if(x == par[x])
			return x;
		else
			return par[x] = root(par[x]);

	}

	bool same(LL x,LL y){
		return (root(x) == root(y));

	}

	void Union(LL x,LL y){
		LL rtx = root(x);
		LL rty = root(y);

		if(rank[rtx] < rank[rty]){
			par[rtx] = rty;
		}
		else{
			par[rty] = rtx;
			if(rank[rtx] == rank[rty]){
				rank[rtx]++;
			}
		}

	}

};

class ST{


};

/*↑マイライブラリ↑*/

LL solveA(){
	LL N,M;
	cin >> N >> M;

	char op;
	cin >> op;

	LL A[N],B[M];

	rep(i,0,M)
		cin >> B[i];

	rep(i,0,N)
		cin >> A[i];


	rep(i,0,N){
		rep(j,0,M){
			if(op == '+'){
				cout << A[i]+B[j] << " ";
			}

			if(op == '*'){
				cout << A[i]*B[j] << " ";
			}

		}

		cout << endl;
	}


	return 0;

}

LL solveB(){
	LL N,M,K;
	cin >> N >> M >> K;

	char op;
	cin >> op;

	LL A[N],B[M];

	LL sumA = 0,sumB = 0;

	rep(i,0,M){
		cin >> B[i];
		sumB = (sumB + B[i]) % K;
	}

	rep(i,0,N){
		cin >> A[i];
		sumA = (sumA + A[i]) % K;
	}


	if(op == '+'){
			cout << ((sumA*M)%K + (sumB*N)%K)%K;

			return 0;

	}

	if(op == '*'){
		cout << (sumA*sumB)%K;
	}

	return 0;
}

LL solveC(){
	LL N,M,K;
	cin >> N >> M >> K;

	char op;
	cin >> op;

	LL A[N],B[M];


	rep(i,0,M){
		cin >> B[i];
	}

	rep(i,0,N){
		cin >> A[i];
	}

	sort(A,A+N);

	LL ans = 0;

	if(op == '+'){
		rep(i,0,M){

			LL ng = -1,ok = N;

			while(ok - ng != 1){
				LL mid = (ng + ok)/2;

				if(A[mid] + B[i] >= K){
					ok = mid;
				}else{
					ng = mid;
				}
			}

			ans += N - ok;

		}

	}

	if(op == '*'){
		rep(i,0,M){

			LL ng = -1,ok = N;

			while(ok - ng != 1){
				LL mid = (ng + ok)/2;

				if(A[mid] * B[i] >= K){
					ok = mid;
				}else{
					ng = mid;
				}

			}

			ans += N - ok;

		}

	}

	cout << ans;

	return 0;
}

LL solveD(){
	LL N,M,K;
	cin >> N >> M >> K;

	char op;
	cin >> op;

	LL A[N],B[M];

	map<LL,LL> anum;

	if(op == '+'){
		rep(i,0,M){
			cin >> B[i];
			B[i] %= K;
			if(B[i] < 0)
				B[i] += K;
		}

		rep(i,0,N){
			cin >> A[i];
			A[i] %= K;
			if(A[i] < 0)
					A[i] += K;

			anum[A[i]]++;
		}

		sort(A,A+N);

		LL ans = 0;

		rep(i,0,M){

				ans +=anum[(K - B[i]) % K];
		}

		cout << ans;
	}

	if(op == '*'){
		map<LL,LL> anum;
		map<LL,LL> bnum;

		rep(i,0,M){
			cin >> B[i];
			B[i] = gcd(B[i],K);
			bnum[B[i]]++;
		}

		rep(i,0,N){
			cin >> A[i];
			A[i] = gcd(A[i],K);
			anum[A[i]]++;
		}

		LL ans = 0;

		REP(a , anum){
			REP(b , bnum){
				if((a.first*b.first) % K == 0){
					ans += a.second*b.second;
				}
			}
		}


		cout << ans;
	}


	return 0;
}

LL solveE(){

	return 0;
}

signed main(){
	//solveA();
	//solveB();
	//solveC();
	solveD();
	//solveE();
	return 0;
}
0