Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Greedy Mathematician

By saurav_paul, soumik9876 · Limits 1s, 512 MB

Once upon a time, there lived a man called Mahi the mathematician. He was banned from his kingdom because of his stupid theories. He moved to another kingdom and started his own shop. As usual, he came up with another stupid theory. Every month he buys N goods for his shop. All the goods have a specific profit A1,A2, A3……An .He pays exactly one good to the kingdom as tax so that the gcd of the profits of the remaining goods are maximized. And surprisingly enough, his theory starts to work this time as he begins to profit more. You want to apply his theory to your shop to increase your profit. You also want to know how many ways you can achieve maximum gcd. N.B. gcd or greatest common divisor of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For example, the gcd of 12 and 16 is 4.


First line will contain an integer N(1< N ≤ 105). The next line will contain N space separated integers A1, A2, A3, …, An (1≤ Ai≤1012).


Print two space separated integers-the maximum possible gcd of the remaining profits and number of ways to achieve maximum gcd.


7 7 7 7
7 4
1 2
2 1



NaN% Solution Ratio


Login to submit

Related Contests

SEC Intra Campus Programming Contest, CSE Fest 2020 Ended at 2020-02-19 11:02:00 +0000 UTC