↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
#define int long long↵
#define ll long long↵
↵
int modmul(int a, int b, int M) {↵
long long ret = a * b - M * (int)(1.L / M * a * b);↵
return ret + M * (ret < 0) - M * (ret >= (ll)M);↵
}↵
int modpow(int b, int e, int mod) {↵
int ans = 1;↵
for (; e; b = modmul(b, b, mod), e /= 2)↵
if (e & 1) ans = modmul(ans, b, mod);↵
return ans;↵
}↵
bool prime(int n) {↵
if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;↵
int A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},↵
s = __builtin_ctzll(n-1), d = n >> s;↵
for (int a : A) { // ^ count trailing zeroes↵
int p = modpow(a%n, d, n), i = s;↵
while (p != 1 && p != n - 1 && a % n && i--)↵
p = modmul(p, p, n);↵
if (p != n-1 && i != s) return 0;↵
}↵
return 1;↵
}↵
int pollard(int n) {↵
auto f = [n](int x) { return modmul(x, x, n) + 1; };↵
int x = 0, y = 0, t = 30, prd = 2, i = 1, q;↵
while (t++ % 40 || __gcd(prd, n) == 1) {↵
if (x == y) x = ++i, y = f(x);↵
if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;↵
x = f(x), y = f(f(y));↵
}↵
return __gcd(prd, n);↵
}↵
vector<int> factor(int n) {↵
if (n == 1) return {};↵
if (prime(n)) return {n};↵
int x = pollard(n);↵
auto l = factor(x), r = factor(n / x);↵
l.insert(l.end(), begin(r), end(r));↵
return l;↵
}↵
struct custom_hash { // Credits: https://codeforces.net/blog/entry/62393↵
static uint64_t splitmix64(uint64_t x) {↵
// http://xorshift.di.unimi.it/splitmix64.c↵
x += 0x9e3779b97f4a7c15;↵
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;↵
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;↵
return x ^ (x >> 31);↵
}↵
size_t operator()(uint64_t a) const {↵
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
return splitmix64(a + FIXED_RANDOM);↵
}↵
template<class T> size_t operator()(T a) const {↵
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
hash<T> x;↵
return splitmix64(x(a) + FIXED_RANDOM);↵
}↵
template<class T, class H> size_t operator()(pair<T, H> a) const {↵
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
hash<T> x;↵
hash<H> y;↵
return splitmix64(x(a.f) * 37 + y(a.s) + FIXED_RANDOM);↵
}↵
};↵
template<class T, class H> using umap = unordered_map<T, H, custom_hash>;↵
template<class T> using uset = unordered_set<T, custom_hash>;↵
↵
↵
int n;↵
vector<pair<int, int>> a;↵
vector<set<int>> hld;↵
umap<int, int> cnt;↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
cin >> n;↵
a.resize(n);↵
for(auto& i: a) {↵
cin >> i.first >> i.second;↵
}↵
for(int i = 0; i < n; ++i) {↵
vector<int> hld1, hld2;↵
hld1 = factor(a[i].first);↵
hld2 = factor(a[i].second);↵
set<int> se;↵
for(auto& j: hld1) {↵
se.insert(j);↵
}↵
for(auto& j: hld2) {↵
se.insert(j);↵
}↵
hld.emplace_back(se);↵
}↵
for(auto& i: hld) {↵
for(auto& j: i) {↵
++cnt[j];↵
}↵
}↵
for(auto& i: cnt) {↵
if(i.second == n) {↵
cout << i.first << "\n";↵
return 0;↵
}↵
}↵
cout << -1 << "\n";↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
This is the code. The factorization algorithm is taken from KACTL, same with the Miller-Rabin and with the modmul and the modpow.↵
↵
#My thought process:↵
If we take each pair and then prime factorize each of the numbers in the pair and then take the union of those prime factors and then for each union, we count the number of primes and if there are $n$ of those primes in the pairs then, at least one number from each pair will be divisible by that number.↵
↵
#Complexity↵
Since the prime factorization is $O(n^{\frac{1}{4}})$, and we are doing $O(n)$ of them and there are at most 30 prime factors for a number $\le 2 \cdot 10^{9}$, the complexity is about $O(n \cdot n^{\frac{1}{4}})$ or $O(n^{\frac{5}{4}})$. This complexity should suffice for $n \le 150,000$↵
↵
Please let me know if there is a section where it is not clear. Thanks for reading the blog.
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
#define int long long↵
#define ll long long↵
↵
int modmul(int a, int b, int M) {↵
long long ret = a * b - M * (int)(1.L / M * a * b);↵
return ret + M * (ret < 0) - M * (ret >= (ll)M);↵
}↵
int modpow(int b, int e, int mod) {↵
int ans = 1;↵
for (; e; b = modmul(b, b, mod), e /= 2)↵
if (e & 1) ans = modmul(ans, b, mod);↵
return ans;↵
}↵
bool prime(int n) {↵
if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;↵
int A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},↵
s = __builtin_ctzll(n-1), d = n >> s;↵
for (int a : A) { // ^ count trailing zeroes↵
int p = modpow(a%n, d, n), i = s;↵
while (p != 1 && p != n - 1 && a % n && i--)↵
p = modmul(p, p, n);↵
if (p != n-1 && i != s) return 0;↵
}↵
return 1;↵
}↵
int pollard(int n) {↵
auto f = [n](int x) { return modmul(x, x, n) + 1; };↵
int x = 0, y = 0, t = 30, prd = 2, i = 1, q;↵
while (t++ % 40 || __gcd(prd, n) == 1) {↵
if (x == y) x = ++i, y = f(x);↵
if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;↵
x = f(x), y = f(f(y));↵
}↵
return __gcd(prd, n);↵
}↵
vector<int> factor(int n) {↵
if (n == 1) return {};↵
if (prime(n)) return {n};↵
int x = pollard(n);↵
auto l = factor(x), r = factor(n / x);↵
l.insert(l.end(), begin(r), end(r));↵
return l;↵
}↵
struct custom_hash { // Credits: https://codeforces.net/blog/entry/62393↵
static uint64_t splitmix64(uint64_t x) {↵
// http://xorshift.di.unimi.it/splitmix64.c↵
x += 0x9e3779b97f4a7c15;↵
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;↵
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;↵
return x ^ (x >> 31);↵
}↵
size_t operator()(uint64_t a) const {↵
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
return splitmix64(a + FIXED_RANDOM);↵
}↵
template<class T> size_t operator()(T a) const {↵
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
hash<T> x;↵
return splitmix64(x(a) + FIXED_RANDOM);↵
}↵
template<class T, class H> size_t operator()(pair<T, H> a) const {↵
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();↵
hash<T> x;↵
hash<H> y;↵
return splitmix64(x(a.f) * 37 + y(a.s) + FIXED_RANDOM);↵
}↵
};↵
template<class T, class H> using umap = unordered_map<T, H, custom_hash>;↵
template<class T> using uset = unordered_set<T, custom_hash>;↵
↵
↵
int n;↵
vector<pair<int, int>> a;↵
vector<set<int>> hld;↵
umap<int, int> cnt;↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
cin >> n;↵
a.resize(n);↵
for(auto& i: a) {↵
cin >> i.first >> i.second;↵
}↵
for(int i = 0; i < n; ++i) {↵
vector<int> hld1, hld2;↵
hld1 = factor(a[i].first);↵
hld2 = factor(a[i].second);↵
set<int> se;↵
for(auto& j: hld1) {↵
se.insert(j);↵
}↵
for(auto& j: hld2) {↵
se.insert(j);↵
}↵
hld.emplace_back(se);↵
}↵
for(auto& i: hld) {↵
for(auto& j: i) {↵
++cnt[j];↵
}↵
}↵
for(auto& i: cnt) {↵
if(i.second == n) {↵
cout << i.first << "\n";↵
return 0;↵
}↵
}↵
cout << -1 << "\n";↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
This is the code. The factorization algorithm is taken from KACTL, same with the Miller-Rabin and with the modmul and the modpow.↵
↵
#My thought process:↵
If we take each pair and then prime factorize each of the numbers in the pair and then take the union of those prime factors and then for each union, we count the number of primes and if there are $n$ of those primes in the pairs then, at least one number from each pair will be divisible by that number.↵
↵
#Complexity↵
Since the prime factorization is $O(n^{\frac{1}{4}})$, and we are doing $O(n)$ of them and there are at most 30 prime factors for a number $\le 2 \cdot 10^{9}$, the complexity is about $O(n \cdot n^{\frac{1}{4}})$ or $O(n^{\frac{5}{4}})$. This complexity should suffice for $n \le 150,000$↵
↵
Please let me know if there is a section where it is not clear. Thanks for reading the blog.
