saiprajna_nayak's blog

How to solve this problem ?? [easy -med question]
By saiprajna_nayak, 9 years ago, In English

I am pretty new unfortunately. So this is the question i just can't figure out how to solve.

Statement:

Sveta loves chocolates. More specifically she loves to have Gems chocolates. In PET most people love numbers, so here the different types of Gems are distinguished by numbers(unlike the boring blue/green/red colors).

As you already know, PET is a magical place. So every Wednesday, the Gems in the packet mysteriously increase in quantity. While most people never bothered to find out the reason, Sveta, being a smart girl, decoded the pattern in which this weird phenomenon occurred. She noticed that if the Gem had a number N, it would split into Gems with numbers in range of 2 to N-1 if the numbers were a factor of N. This splitting would go on until there was no way to split any remaining Gems in this manner.

Now Puru wants to know the final sum of numbers of the Gems after magical transformation in order to impress Sveta. Help him out.

Input:

First line contains T number of testcases

Next line contains N, the number of Gems in the packet Sveta has bought

Next line contains N integers, denoting the number assigned to each gem.

Output:

Print the sum of numbers of all gems after the magical transformation has taken place.

Constraints:

1 <= T <= 1000

1 <= N <= 40

2 <= number assigned to gems <= 10^4

Sample:

Input:

1

2

2 12

Output:

14

Explanation:

Now the first gem with value 2 can't divide as per the rules, so it stays as it is. Gem with number 12 divides into 4 gems with numbers 2,3,4 and 6. Now gems 2 and 3 cant divide, however gems 4 and 6 can divide into gems 2 and gems 2,3 respectively. Now the gems can't divide anymore and the magical transformation ends. So the result is 2 + 2+3 + 2 + 2+3 = 14

  • Vote: I like it
  • +19
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

if i is not a prime number:
DP[i] = DP[x1] + DP[x2] + DP[x3] + ... + DP[xm] where xj is a factor of i and 1 < xj < i
else
DP[i] = i

You can do this pre-calculation for all numbers in

Then you can answer each test case in O(n)

The precalculation can be done in O(maxNumber * log(maxNumber)) , after calculating DP[i] , you add DP[i] to all multiples of i , in O(maxNumber + maxNumber / 2 + maxNumber / 3...) = O(maxNumber * log(maxNumber))

→ Reply