- Pre-calculate all prime divisor for each number. (sieve)
- For each number X get its simplest form (i.e. p1 * p2 * p3 instead of p1^a1 * p2^a2 * p3^a3) because for the current problem these are the same.
- Remember how many of the same numbers are (after translation) (There can be maximum ~ 121K of such numbers)
- Initialise DSU (disjoint union set) structures.
- Break early if the array contains number “1” - as all other numbers will be just joined together into single group.
- Allocate as required bit-set array for each prime (sufficient length to cover 121K bits) there are maximum <20K such primes so total memory ~ 256M max. The structure contains up to 121K/64 ~ 1900 long long ints. For each bit-set set i-th bit if the i-th number contains this prime.
- Sort the vector of the numbers with less primes first , then sort by primes themselves.
- Now run cycle from 0 to Nx(the new N which is <= original N) and for each number - get primes that are in this number and on the fly do OR of the bit-sets for these primes.
- Run it for range i+1,Nx, but obviously /64 as each long long int is 64 bit
- Skip any if the current qword is all 1s, If not - run bit mask to check which number is free of primes from x-ith. Then just do union of x and y
- Break early if total number of unions is 1.
- At the end count number of unions and for each union which is size 1 and not united to anything add its size (number of these numbers) minus one to the results. I.e. if there are 3 identical primes in the original array and they are not joined - then we have 2 more free groups to add. Report the final result.
Tons of opportunities for optimisation, but actually not required as the max time ~ 0.15 seconds.
I really liked the problem. Thanks to the author.