problem link:- https://codeforces.me/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.
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.