problem link:- https://mirror.codeforces.com/problemset/problem/1881/D
here we have to choose two element in the array let ai,aj and choose a divisor of ai let x and replace ai=ai/x ans aj=aj*x;
after some operation we have to make all the element equal in that array
now let consider an array of two elements a1,a2 now let ai=a1 and aj=a2 x the divisor a1
==>let say a1=a1/x and a2=a2*x; ==>now a1/x=a2*x now multiply these two we get (a1/x)*(a2*x)=a1*a2;
we can generalise after all the operation when we multiply all the elements we get a1*a2*a3*a4...... so we can generalise if the nth root of a1*a2*a3....*an is a whole number then return yes otherwise return no; I don't no how to implement this idea..... also please clarify that the idea is right or wrong.
Auto comment: topic has been updated by saptarshikuar2003 (previous revision, new revision, compare).
Well if you multiply all array elements, you may not be able to fit it in any data type.
I have better approach lets say all the elements have some factors if we map all these factors together, we should get number of ith factor a multiple of n.
This is same as taking nth root.
Yes your approach is right, to implement this here is a simple idea — for example there are 3 elements in array: suppose — a1 has prime factorisation p1^q1*p2^q2*p3^q3 a2 has prime factorisation p1^q4*p2^q5*p4^q6 a3 has prime factorisation p1^q1*p3^q7*p4^q8 (p1,p2,p3,p4 are primes and q1...q8 are constants) Now total count of each primes : cnt[p1] = q1+q1+q4, cnt[p2] = q2+q5, cnt[p3] = q3+q7, cnt[p4] = q6+q8 Now these total counts basically represent the counts of primes of prime factorisation(if hypothetically we have multiplied a1*a2*a3(generalized a1*a2..*an)) Now if each individual count % n == 0 this means we can equally divide this prime in n positions ..if not then not possible to divide equally.
For finding prime factorization there is simple function in GFG, and to store counts you can use map.
Simply you are doing the same thing, like if you think when the question is asking to equalize, what it's saying is to distribute all the prime factors in equal amount to each index
Thus after multiplying them we get all the number as same
which is same as in your idea you are first taking product of all ==> summing up power of each prime factors and then taking nth root overall doing the same operation of distributing the prime
just the problem could be of overflow if you go this way better you can compute the occurrences of a prime factor and store in a map then distributing would do the task.
submission — https://mirror.codeforces.com/contest/1881/submission/288693960
Thank you all for making the analysis much better I got to know about the implementation.