TopCoder problem "DecorationDay" used in TCHS08 Round 1 (Division I Level Three)



Problem Statement

    

Partuki and Haverta are playing a game. Partuki places several groups of coins in front of Haverta, and asks her to select one or more of the groups. The groups must be selected so that counts of coins in them do not share any common divisors greater than 1. For example, you could choose a group of 4 coins, a group of 3 coins, and a group of 2 coins because 4, 3 and 2 share no common divisors greater than 1. However, you could not chose a group of 4 coins and a group of 2 coins because 4 and 2 share the common divisor 2.

You are given a int[] groups, each element of which is the number of coins in a single group. Determine the number of different ways in which Haverta can make a valid selection, and return this number modulo 10000003.

 

Definition

    
Class:DecorationDay
Method:howMany
Parameters:int[]
Returns:int
Method signature:int howMany(int[] groups)
(be sure your method is public)
    
 

Constraints

-groups will contain between 1 and 50 elements, inclusive.
-Each elements of groups will be between 1 and 100000, inclusive.
 

Examples

0)
    
{2, 4, 3}
Returns: 3
There are 3 valid selections - {2, 3}, {4, 3} and {2, 4, 3}.
1)
    
{2, 2, 2, 4}
Returns: 0
Groups in any valid selection share the common divisor 2, so there are no valid selections.
2)
    
{2, 6, 15}
Returns: 2
Haverta can choose {2, 15} or {2, 6, 15}.
3)
    
{2, 5, 98872, 23298, 32872, 23111}
Returns: 45
4)
    
{2, 2, 3}
Returns: 3
Here there are three ways to make a selection:
  • pile 0 (2 coins) and pile 2 (3 coins);
  • pile 1 (2 coins) and pile 2 (3 coins);
  • all three piles.
5)
    
{1}
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8213

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11153&pm=8213

Writer:

vlad_D

Testers:

PabloGilberto , Olexiy , ivan_metelsky , andrewzta

Problem categories:

Dynamic Programming