Submission #45095866

Source Code Expand

#include <algorithm>
#include <iostream>
#include <numeric>
#include <unordered_map>
using namespace std;

unordered_map<int, int> C(100000);

int main()
{
	int N; cin >> N;
	int M = 1000000000;
	for (int i = 0; i < N; ++i) {
		int a; cin >> a;
		int b = 1, c = a;
		while (b <= c) {
			if (a == b * c) {
				int& c0 = C[b];
				c0 = c0 ? gcd(c0, c) : c;
				int& b0 = C[c];
				b0 = b0 ? gcd(b0, b) : b;
			}
			c = a / ++b;
		}
		M = min(a, M);
	}
	int R = count_if(C.begin(), C.end(), [M](decltype(C)::value_type cc){ return cc.first <= M && cc.second == 1; });
	cout << R << endl;
	return 0;
}

Submission Info

Submission Time
Task F - GCD or MIN
User ds14050
Language C++ (Clang 10.0.0)
Score 600
Code Size 628 Byte
Status AC
Exec Time 192 ms
Memory 9844 KiB

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 112 ms 5140 KiB
big_answer_01.txt AC 92 ms 5112 KiB
big_answer_02.txt AC 96 ms 5140 KiB
big_answer_03.txt AC 83 ms 4968 KiB
handmade_00.txt AC 2 ms 3408 KiB
handmade_01.txt AC 2 ms 3408 KiB
many_divisors_00.txt AC 169 ms 9844 KiB
primes_00.txt AC 119 ms 3312 KiB
primes_01.txt AC 116 ms 3428 KiB
primes_02.txt AC 85 ms 3268 KiB
primes_03.txt AC 84 ms 3396 KiB
random_00.txt AC 122 ms 4464 KiB
random_01.txt AC 122 ms 4372 KiB
random_02.txt AC 123 ms 4364 KiB
random_03.txt AC 128 ms 4356 KiB
random_04.txt AC 120 ms 4328 KiB
random_05.txt AC 46 ms 3704 KiB
random_06.txt AC 50 ms 3816 KiB
random_07.txt AC 78 ms 4016 KiB
random_08.txt AC 76 ms 4040 KiB
random_09.txt AC 32 ms 3696 KiB
same_00.txt AC 155 ms 3404 KiB
same_01.txt AC 154 ms 3416 KiB
same_02.txt AC 8 ms 3256 KiB
same_03.txt AC 175 ms 3256 KiB
same_04.txt AC 192 ms 3396 KiB
same_05.txt AC 170 ms 3248 KiB
sample_01.txt AC 2 ms 3376 KiB
sample_02.txt AC 2 ms 3208 KiB
sample_03.txt AC 2 ms 3416 KiB
semiprimes_00.txt AC 135 ms 3268 KiB
semiprimes_01.txt AC 137 ms 3408 KiB
semiprimes_02.txt AC 138 ms 3356 KiB
semiprimes_03.txt AC 84 ms 3428 KiB
semiprimes_04.txt AC 128 ms 3212 KiB
semiprimes_05.txt AC 31 ms 3408 KiB