PROBLEM LINK:
Author: Varun Singh
DIFFICULTY:
EASY
PREREQUISITES:
Number Theory, Fast Exponentiation
PROBLEM:
Given a square matrix of order x and the sum of all the elements s, fill the matrix such that the product of all the elements is maximum.
QUICK EXPLANATION:
Given the sum of two numbers, their product is maximum when both the numbers are equal.Hint Now find the desired element to be inserted in the matrix, say K = sum / x^2. The ans will be K^{x^2}. Since the result will be extremely large, use fast modular exponentiation.
EXPLANATION:
Using number theory, we know that given the sum of two numbers, their product is maximum when both the numbers are equal.Hint So we now know that each cell in the matrix will have the same element, in order to maximize the product. To find the desired element, say K, we divide the given sum by the number of elements present i.e K = sum / x^2. Now to find the product of all the elements, we just have to find K^{x^2}. Since the result will be extremely large, we will use fast modular exponentiation to calculate the result.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.