CareerCup

I am sorry. One correction. k^2 ranges from 1 - 10^10.

Is there a condition like a != b != k

brute force: a start from 1 to k. Find all a's, we'll automatically get corresponding b's as k2/a. Time complexity is O(k).

if at all, we could decompose k into its primefactors, say a1^b1,a2^b2....an^bn, then k2 will be a1^2b1,a2^2b2....an^2bn. Now, we need to place n distinct numbers (a1...an) in 2b1+2b2+....+2bn bins ...it's a permutations problem. Someone good in math, pls solve and explain the steps in detail.

unsigned long long result = 0;
unsigned long i;
for (i = 1; i<=TEN_OF_FIVE; i++) {
result += TEN_OF_TEN / i;
}
for (i = 1; i<TEN_OF_FIVE; i++) {
result += i * (TEN_OF_TEN/i - TEN_OF_TEN/(i+1));
}

can you clarify the problem? k is not given? it is asking for a k which has most sets?

I wonder if one thing we're supposed to notice is that if you square 10^10, you exceed the maximum value of even a 64 bit long integer. So, therefore, you should compare sqrt(a*b) to k, as opposed to comparing a*b to k^2. And then you get into floating point math, not integer math, so you should allow for some small difference in the comparison.

Let S_k = { (a, b) | a * b = k^2 },

and if k = p_1^r_1 ... p_t^r_t(pow of different primes), then

#S_k = (2 * r_1 + 1) * ... * (2 * r_t + 1).

Just find max (#S_k for all k in 1, ...10^5).

O(1) space
O(n) time complexity;

void func(int *arr, int n, unsigned int k)
{
   long long req = (long long)k * (long long)k;
   int i = 0, j = n -1;
   bool found = false;
   while (i < j) {
         long long mul = (long long)arr[i] * (long long)arr[j];
         if (mul < req) {
             i++;
         } else if (mul > req) {
            j--;
         } else {
           
           found = true;
           break;
         }
   }

   if (found == true) {
       printf("%d %d\n", arr[i], arr[j]);
   } else {
       printf("Not found\n");
   }
}