The Greedy Mathematician

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.


This is a companion discussion topic for the original entry at https://toph.co/p/the-greedy-mathematician