#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";
}
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).
Is there something that I said wrong? Why all the downvotes?
Why are you making a post about a TLE? The time complexity of your solution is $$$O(n^\frac{5}{4} log(n) log(max(a_i, b_i))$$$ Plugging values in, your code does around $$$1.5e9$$$ operations.
Why is there a $$$log(max(a_{i}, b_{i}))$$$?
there are at most 30 prime factors for a number ≤2⋅10^9quoted from your blog.When doing time complexity analysis, you can't just say
I don't think that that would matter much.Lets look at the bottleneck of the code.
We are doing $$$O(n)$$$ factors which is $$$O(n^{\frac{5}{4}}).$$$ Then, since there are at most 30 prime factors of a number $$$\le 2 \cdot 10^{9}$$$, the set which stores the union of the prime factors is at most $$$O(log(60))$$$. So I argue that the complexity is $$$O(n^{\frac{5}{4}} \cdot log(60))$$$
Oops. Actually the complexity is $$$O(n^\frac{5}{4} k \log(k))$$$ where $$$k$$$ is the maximum amount of prime factors a number can have. This is because you iterate over all prime factors of the pairs in each iteration. Evaluating with $$$k = 60$$$, this totals to $$$10^9$$$. Also, the constant factor of prime factorizing is probably somewhat high.
Why is it multiplied by $$$O(k)$$$?
This is because you iterate over all prime factors of the pairs in each iterationIf I use an
unordered_setthen I can remove the $$$O(log(60))$$$.for(auto& j: hld1) {I think you doesn't need to use such a troublesome way to solve this problem... it can be much easier.
You can just first calculate the prime factor of the first pair and store it, then when you key in the other pairs, delete the prime factor that work to both numbers of the pair. Then, if there is no prime factor left, print
-1, otherwise print the number.I know there are other people who use the algorithm and pass it, so maybe that's all the reason of all the downvotes...
Here I've just accepted this problem using this algorithm.
You can see my code here
I know of such a solution, but sometimes I want to try a new idea that I have not had before and try it out. This puzzles me as to why the program runs too slow. The complexity is as stated in the blog, and it should work for $$$n \le 150,000$$$.