Submission #20276930


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

int N;
int A[2000 + 10];

int gcd(int a, int b) {
	if (a % b == 0)return b;
	return gcd(b, a % b);
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	map<int, int> M;
	for (int i = 0; i < N; i++) {
		for (int j = 1; j * j <= A[i]; j++) {
			if (A[i] % j == 0) {
				if (M[j] == 0)
					M[j] = A[i];
				else M[j] = gcd(M[j], A[i]);

				if (M[A[i] / j] == 0)
					M[A[i] / j] = A[i];
				else M[A[i] / j] = gcd(M[A[i] / j], A[i]);
			}
		}
	}

	int minA = *min_element(A, A + N);
	int ans = 0;
	for (auto it = M.begin(); it != M.end(); it++) {
		if ((*it).first <= minA && (*it).first == (*it).second)
			ans++;
	}
	cout << ans << endl;

	return 0;
}

Submission Info

Submission Time
Task F - GCD or MIN
User Sen
Language C++ (GCC 9.2.1)
Score 600
Code Size 815 Byte
Status AC
Exec Time 544 ms
Memory 11476 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All big_answer_00.txt, big_answer_01.txt, big_answer_02.txt, big_answer_03.txt, handmade_00.txt, handmade_01.txt, many_divisors_00.txt, primes_00.txt, primes_01.txt, primes_02.txt, primes_03.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, same_00.txt, same_01.txt, same_02.txt, same_03.txt, same_04.txt, same_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, semiprimes_00.txt, semiprimes_01.txt, semiprimes_02.txt, semiprimes_03.txt, semiprimes_04.txt, semiprimes_05.txt
Case Name Status Exec Time Memory
big_answer_00.txt AC 232 ms 5952 KB
big_answer_01.txt AC 222 ms 5908 KB
big_answer_02.txt AC 210 ms 6060 KB
big_answer_03.txt AC 204 ms 6112 KB
handmade_00.txt AC 2 ms 3612 KB
handmade_01.txt AC 2 ms 3656 KB
many_divisors_00.txt AC 232 ms 11476 KB
primes_00.txt AC 113 ms 3704 KB
primes_01.txt AC 109 ms 3692 KB
primes_02.txt AC 82 ms 3688 KB
primes_03.txt AC 81 ms 3636 KB
random_00.txt AC 125 ms 4860 KB
random_01.txt AC 127 ms 4648 KB
random_02.txt AC 127 ms 4680 KB
random_03.txt AC 126 ms 4680 KB
random_04.txt AC 125 ms 4780 KB
random_05.txt AC 52 ms 3872 KB
random_06.txt AC 52 ms 3944 KB
random_07.txt AC 80 ms 4268 KB
random_08.txt AC 81 ms 4240 KB
random_09.txt AC 33 ms 3916 KB
same_00.txt AC 146 ms 3652 KB
same_01.txt AC 146 ms 3612 KB
same_02.txt AC 2 ms 3668 KB
same_03.txt AC 168 ms 3552 KB
same_04.txt AC 544 ms 3640 KB
same_05.txt AC 162 ms 3440 KB
sample_01.txt AC 2 ms 3564 KB
sample_02.txt AC 2 ms 3572 KB
sample_03.txt AC 3 ms 3548 KB
semiprimes_00.txt AC 132 ms 3736 KB
semiprimes_01.txt AC 130 ms 3740 KB
semiprimes_02.txt AC 130 ms 3616 KB
semiprimes_03.txt AC 83 ms 3652 KB
semiprimes_04.txt AC 124 ms 3588 KB
semiprimes_05.txt AC 37 ms 3688 KB