Submission #968999


Source Code Expand

#include <bits/stdc++.h>
using namespace std;


vector<long long> getDivisor(long long n){
	vector<long long> ret;
	for(long long i=1;i*i<=n;i++){
		if(n%i==0){
			ret.push_back(n/i);
			if(i != n/i)ret.push_back(i);
		}
	}
	sort(ret.begin(),ret.end());
	return ret;
}

int cnt[114514];
void solve(long long N, long long K, vector<long long> A){
	auto ds = getDivisor(K);
	unordered_map<int,vector<int> > ok;
	for(int i = 0 ; i < ds.size() ; i++){
		for(int j = 0 ; j < ds.size() ; j++)
			if( ds[i] % ds[j] == 0 )
				ok[ds[i]].push_back(j);
	}
	//cout << ds.size() << endl;
	int zero = 0;
	long long ans = 0;
	for(int i = 0 ; i < A.size() ; i++){
		int w = __gcd(K,A[i]);
		int a = K / w;
		ans += cnt[lower_bound(ds.begin(),ds.end(),a)-ds.begin()]; 
		
		if( A[i] == 0 ) zero++;
		else{
			for( auto &&j : ok[w] )
				cnt[j]++;
		}
	}
	
	cout << ans << endl;
	
}



int main(){	
	long long N;
	long long K;
	cin >> N;
	//N = 200000;
	vector<long long> A(N-1+1);
	cin >> K;
	//K = 735134400;
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&A[i]);
		//A[i] = 735134400;
	}
	solve(N, K, A);
	return 0;
}

Submission Info

Submission Time
Task C - ロト2
User kyuridenamida
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1165 Byte
Status AC
Exec Time 115 ms
Memory 4224 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:56:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&A[i]);
                      ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 25
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_random_01.txt, 10_random_02.txt, 10_random_03.txt, 10_random_04.txt, 10_random_05.txt, 20_max_01.txt, 20_max_02.txt, 20_max_03.txt, 20_max_04.txt, 20_max_05.txt, 30_overflow_01.txt, 30_overflow_02.txt, 40_dmax_01.txt, 40_dmax_02.txt, 40_dmax_03.txt, 50_prime_01.txt, 50_prime_02.txt, 50_prime_03.txt, 60_prime_pow_01.txt, 60_prime_pow_02.txt, 60_prime_pow_03.txt, 70_one_01.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 3 ms 256 KB
00_example_02.txt AC 3 ms 256 KB
00_example_03.txt AC 3 ms 256 KB
10_random_01.txt AC 3 ms 256 KB
10_random_02.txt AC 3 ms 256 KB
10_random_03.txt AC 3 ms 256 KB
10_random_04.txt AC 3 ms 256 KB
10_random_05.txt AC 3 ms 256 KB
20_max_01.txt AC 47 ms 3328 KB
20_max_02.txt AC 43 ms 3328 KB
20_max_03.txt AC 55 ms 3328 KB
20_max_04.txt AC 44 ms 3328 KB
20_max_05.txt AC 62 ms 3328 KB
30_overflow_01.txt AC 45 ms 3328 KB
30_overflow_02.txt AC 45 ms 3328 KB
40_dmax_01.txt AC 114 ms 4224 KB
40_dmax_02.txt AC 115 ms 4224 KB
40_dmax_03.txt AC 114 ms 4224 KB
50_prime_01.txt AC 44 ms 3328 KB
50_prime_02.txt AC 49 ms 3328 KB
50_prime_03.txt AC 54 ms 3328 KB
60_prime_pow_01.txt AC 58 ms 3328 KB
60_prime_pow_02.txt AC 54 ms 3328 KB
60_prime_pow_03.txt AC 54 ms 3328 KB
70_one_01.txt AC 34 ms 3328 KB