Orac and LCM ( GCD and LCM property Help)

, ,

Question link : https://codeforces.com/contest/1350/problem/C

In the above question one of Property of GCD and LCM is used

For integers N1, …, Nk, k ≥ 2,
gcd(lcm(N1, M), lcm(N2, M), …, lcm(Nk, M)) = lcm(gcd(N1, …, Nk), M).

I need Proof for this , can anyone help @aryanc403 @l_returns @ssjgz @striver_79

1 Like

1.https://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml
2.https://proofwiki.org/wiki/GCD_and_LCM_Distribute_Over_Each_Other
may be these can help you.

1 Like

I read them … but i need some mathematical proof …if someone help then i appreciate more :slight_smile:

Consider a prime p. Let \alpha_i denote the power of p in the prime factorisation of N_i and \beta denote the power of p in the prime factorisation of M.
We can see that the power of p in the left expression =min(max(\alpha_i, \beta))
Similarly, the power of p in the right expression is
=max(min(\alpha_i), \beta).

We can see that Lhs must be at least \beta, as no term is allowed to be less than \beta. We can see that if LHS is greater than \beta and is equal to x, all \alpha_i must be larger than \beta, of whose minimum should be x. Therefore we can claim the two expressions are equivalent since the power of all primes is equal.

I’m assuming you know GCD of two numbers \Pi p_i^{\alpha_i}\ and\ \Pi p_i^{\beta_i} is \Pi p_i^{min(\alpha_i, \beta_i)} and their LCM is \Pi p_i^{max(\alpha_i, \beta_i)}

1 Like

Explain this more :pray:

Can \max(\alpha_i, \beta) be less than \beta? It cannot.

Can \min(\max(\alpha_i, \beta)) be less than \beta. It cannot since all terms are \ge \beta.

Can there exist an \alpha_i\le\beta such that \min(\max(\alpha_i, \beta))\gt\beta . It cannot since \max(\alpha_i, \beta) is \beta for at least one i and therefore the minimum is \le \beta.

If all \alpha_i>\beta then \min(\max(\alpha_i, \beta))=\min(\alpha_i). This is because if \alpha_i>\beta then \max(\alpha_i, \beta)=\alpha_i.

Therefore we can deduce our answer is \min(\alpha_i) if \min(\alpha_i)>\beta, otherwise it’s \beta, which is max(min(\alpha_i), \beta). Therefore the 2 equations are equivalent.

1 Like

Bro …one thing may be u think i 'm dumb…but u proved LHS = RHS …but let’s suppose i don’t know RHS … so how can u deduce the result :pray:

I didn’t explicitly find the RHS while I was solving. So I don’t know how to do it like that.
We have to find GCD({LCM({a_i,a_j})\ |\ i<j})
Let us consider a prime p such that the largest power of p that divides a_i is \alpha_i. We have to find min(max(\alpha_i, \alpha_j))\ |\ i<j. We can see that This is the second smallest value of \alpha_i.
Proof :
We can ignore the i<j rule as max(\alpha_i, \alpha_j)=max(\alpha_j, \alpha_i). We just have to make sure i\not=j. So let us sort the array. Now \alpha_i denotes the ith largest value of \alpha. We can see that the max(\alpha_0, \alpha_1)=\alpha_1. This is also the smallest possible value we can get. Therefore the power of p in GCD({LCM({a_i,a_j})\ |\ i<j}) is \alpha_1. We can compute this for all p, and calculate \Pi p^{\alpha_1} for all primes.

To solve it fast, we keep a vector containing \alpha_i for all p. We do not add \alpha_i, if it is 0. If the size of the vector at the end is n-1, then \alpha_1 is the minimum element, since \alpha_0=0 is ignored.
If it is n, then it is the second minimum element.
If it is lesser than n-1 then at least 2 values in \alpha are 0, therefore the power of p is also 0.

My submission

1 Like

I use same approach bro…but i need some proof for above property …like how u reduce the LHS to RHS ?

Can you tell me which LHS and RHS?

LHS :

RHS:

I went from LHS to RHS for that equation already Here. There is no better way to do it. I’ve not used the RHS at all. You can’t just solve equations without thinking at all. You have to find what it is equivalent to and simplify it until you are able to think of an algorithm that can solve this within the constraints.

2 Likes