#!/usr/bin/env python# Interesting Numbers solution by Phil Bordelonimportmathimportosimportsys# Debug?DEBUG = os.getenv("DEBUG", False)defisprime(n):# One isn't prime.ifn == 1:returnFalse# Even numbers aren't prime unless they're 2.ifn == 2:returnTrueelifn % 2 == 0:returnFalse# Okay; loop through all numbers less than or equal to the square root# the number to find factors. Assume primality; if it's not prime,# break out cos we're done.is_prime = True highest_factor =int(math.sqrt(n))foriinrange(3, highest_factor + 1):ifn % i == 0: is_prime = Falsebreakreturnis_primedefispower(n, power):# Find the 1/powerth root of n; this is a real number.real_root = math.pow(n, 1.0/power)# Find if its integer component is precisely n. We do this by multiplying# back up. The problem is that the int() cast may put us not at the# precise root, thanks to the imprecision of floating point. So we cheat# by testing the number returned by int() along with the one above it;# since int() rounds towards zero, it could potentially be one higher.int_root =int(real_root)fortest_valuein(int_root, int_root + 1): curr_val = test_valueforiinrange(power - 1): curr_val *= test_value# Return whether or not that got us back to n.ifcurr_val == n:# Yup. Return the root.returntest_value# No, this is not an exact power. Return 0.return0defdigit_sum(n):# This simple little function calculates the sum of the digits of a number.curr_num = n sum = 0whilecurr_num >= 1: digit = curr_num % 10 sum += digit curr_num /= 10returnsumdefdigit_mult(n):# This function calculates the multiplication of the digits.curr_num = n mult = 1whilecurr_num >= 1: digit = curr_num % 10 mult *= digit curr_num /= 10returnmultif"__main__" == __name__:# Instead of duplicating work, we're going to track the data that is# not collection-sensitive in a dictionary for later reuse. This# makes the program get more efficient, not less, across data sets.num_dict = {} dataset_count =int(sys.stdin.readline())fordataset_loopinrange(dataset_count):# Load the elements into the list.data_list = [] list_len =int(sys.stdin.readline())foriinrange(list_len): data_list.append(int(sys.stdin.readline()))# Sort the list ...data_list.sort()# Now go through them and count the pertinent elements. Keep# track of the most attributes found so far.most_attributes = 0 attribute_list = []# First pass; calculate values for numbers we haven't seen before.forentryindata_list:ifentrynotinnum_dict:# All right. We will now calculate various "static" values,# which do not depend on what numbers are in a given collection.# These are things like primality, whether the number is a# square, cube, or quad, and what the sum and multiplication of# its digits are (and whether it is a multiple of those).this_dict = {} count = 0# Primality doesn't need to be tracked, just counted.ifisprime(entry):ifDEBUG:# Powers, on the other hand, are worth tracking, as we can use# the roots in the later per-collection phase.forpowerin(2, 3, 4): power_result =ispower(entry, power)ifpower_result:ifDEBUG:# The value of the sum and multiply bits is also worth saving.sum =digit_sum(entry)ifentry % sum == 0:ifDEBUG:# Whether or not it's a multiple of its own sum, we need to store# it, so we can see if other numbers are a multiple of its sum in# the per-collection phase.this_dict["sum"] = sum mult =digit_mult(entry)ifmult > 0andentry % mult == 0:ifDEBUG:# Much like the sum above, we need to store this value for the# per-collection phase.this_dict["mult"] = mult# Done calculating all of the "static" values. Store!this_dict["count"] = count num_dict[entry] = this_dict# Now that we've precalculated various things, loop over the values again.forentryindata_list: this_dict = num_dict[entry]# Start with the count of the default (non-list-dependent) attributes.attribute_count = this_dict["count"]ifDEBUG:# Other-square, -cube, and -quad are trivial. If this number# /is/ a square, cube, or quad, we recorded which number it is# the s/c/q of.forattributein(2, 3, 4):ifattributeinthis_dictandthis_dict[attribute]indata_list:ifDEBUG:# Now we have to loop through the /other/ numbers in the list for# the other attributes.forother_entryindata_list:ifother_entry != entry: other_dict = num_dict[other_entry]# Other-sum-multiple and other-multiple-multiple are similar# to other-square/cube/quad, although there's a mod involved.forattributein("sum", "mult"):ifattributeinother_dict: val = other_dict[attribute]# If the value isn't zero (which only occurs for the# multiplier, and is meant to be ignored), see if this# is a factor of the entry.ifval > 0andentry % val == 0:ifDEBUG:# Lastly, we have factor and multiple.ifother_entry < entryandentry % other_entry == 0:ifDEBUG:elifother_entry > entryandother_entry % entry == 0:ifDEBUG:ifDEBUG:# Record the highest attribute count so far ...ifattribute_count > most_attributes: most_attributes = attribute_count# ... and record /this/ attribute count.attribute_list.append(attribute_count)# Phew. Done. Print out the numbers with the highest attribute count;# there may be more than one, which is why we kept them all around.foriinrange(list_len):ifattribute_list[i] == most_attributes:repr(data_list[i])