common_divisors_1081.cpp (1450B)
1 #include <array> 2 #include <bitset> 3 #include <iostream> 4 5 // This method is very different (and more complicated) than the one used 6 // in the official solution. 7 // First we save in spf[i] the smallest prime number that divides i. 8 // Then we initialize an array d with d[i] being 1 if i is in the input. 9 // Then we loop backwards and we search all divisors of the numbers marked 10 // in d. For each number we encounter, we look at its maximal divisors. 11 // If any of them was already found, we update our candidate solution. 12 // To avoid looking at a divisor more than once, we save in d[i] the 13 // smallest prime we want to continue diving i by to find more divisors. 14 15 constexpr size_t max = 1000001; 16 std::array<size_t, max> spf; // Smallest prime factor of i 17 std::array<size_t, max> d; 18 19 int main() { 20 for (size_t i = 2; i < max; i++) { 21 if (spf[i] != 0) continue; 22 spf[i] = i; 23 for (size_t j = 2; i*j < max; j++) 24 if (spf[i*j] == 0) 25 spf[i*j] = i; 26 } 27 28 size_t n, sol{1}; 29 std::cin >> n; 30 for (size_t i = 0; i < n; i++) { 31 size_t x; 32 std::cin >> x; 33 if (d[x] != 0) sol = std::max(sol, x); 34 d[x] = 1; 35 } 36 37 for (size_t i = max-1; i >= sol; i--) { 38 if (d[i] == 0) continue; 39 40 // Loop over maximal divisors of i 41 size_t y{i}; 42 while (y != 1) { 43 size_t p = spf[y]; 44 if (i/p < sol) break; 45 if (p >= d[i]) { 46 if (d[i/p] != 0) sol = std::max(sol, i/p); 47 d[i/p] = p; 48 } 49 while (y % p == 0) y /= p; 50 } 51 } 52 std::cout << sol << "\n"; 53 }