You are not logged in. Please login at www.codechef.com to post your questions!

×

EASY

# PREREQUISITES:

Sieve of Eratosthenes

# PROBLEM:

Find the winner in a game, which consists of two players, who are picking integers off an array and splitting an integer into two of its factors and replacing the new integers on the array. The end point is when no move can be made.

# QUICK EXPLANATION:

Find the sum of prime factors of all the integers present in the array.

# EXPLANATION:

Basically, the number of times an integer from the array can be subdivided is equal to the number of prime factors of the number – 1. So, if we sum this up for all the numbers in the array, we get the total number of moves that can be played in a game and it is fixed for a given array. Depending on whether this number is odd or even, we get the winner of the game.
The number of prime factors of an integer can be calculated offline by making a little modification to the Sieve code - by adding 1 to all the numbers encountered in the inner loop. However, even solutions which calculate the number of prime factors of an integer online in log(n) time will also pass the test cases.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

asked 02 Nov '17, 23:50

112
accept rate: 0%

 0 Many thanks for the highlighted problem and for the proposed solution, very useful. The problem is really pretty interesting, I think that it will be good to ask it my colleagues and try to solve it together. Again, a lot of thanks, we will post the solution at ﻿this page. answered 15 Nov '17, 13:59 0★joecamp 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,482
×3,706
×301
×197

question asked: 02 Nov '17, 23:50

question was seen: 313 times

last updated: 15 Nov '17, 13:59