Why is this code getting TLE?
Разница между en1 и en2, 306 символ(ов) изменены


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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Qualified 2020-11-14 15:49:38 7 Tiny change: 'n the pair and then take t' -> 'n the pair. Then take t'
en6 Английский Qualified 2020-11-14 06:16:25 114
en5 Английский Qualified 2020-11-14 06:15:16 73
en4 Английский Qualified 2020-11-14 06:08:38 6
en3 Английский Qualified 2020-11-14 06:08:12 18
en2 Английский 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 Английский Qualified 2020-11-14 06:01:15 3727 Initial revision (published)