Why is this code getting TLE?
Difference between en1 and en2, changed 306 character(s)


<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.me/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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Qualified 2020-11-14 15:49:38 7 Tiny change: 'n the pair and then take t' -> 'n the pair. Then take t'
en6 English Qualified 2020-11-14 06:16:25 114
en5 English Qualified 2020-11-14 06:15:16 73
en4 English Qualified 2020-11-14 06:08:38 6
en3 English Qualified 2020-11-14 06:08:12 18
en2 English Qualified 2020-11-14 06:07:37 306 Tiny change: 'c{1}{4}})$.\n\nPle' -> 'c{1}{4}})$ or $O(n^(\frac{5}{4}))$.\n\nPle'
en1 English Qualified 2020-11-14 06:01:15 3727 Initial revision (published)