Prime Game February long challenge 2021 solution with code and explanation

 Prime Game February long challenge 2021 solution with code and explanation  -

Problem statement -

Chef and Divyam are playing a game with the following rules:

• First, an integer X!$X!$ is written on a board.
• Chef and Divyam alternate turns; Chef plays first.
• In each move, the current player should choose a positive integer D$D$ which is divisible by up to Y$Y$ distinct primes and does not exceed the integer currently written on the board. Note that 1$1$ is not a prime.
• D$D$ is then subtracted from the integer on the board, i.e. if the integer written on the board before this move was A$A$, it is erased and replaced by A−D$A-D$.
• When one player writes 0$0$ on the board, the game ends and this player wins.

Given X$X$ and Y$Y$, determine the winner of the game.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first and only line of each test case contains two space-separated integers X$X$ and Y$Y$.

Output

For each test case, print a single line containing the string "Chef" if Chef wins the game or "Divyam" if Divyam wins (without quotes).

Constraints

• 1≤T≤106$1\le T\le {10}^6$
• 1≤X,Y≤106$1\le X,Y\le {10}^6$

Subtasks

Subtask #1 (5 points): Y=1$Y=1$

Subtask #2 (10 points):

• 1≤T≤102$1\le T\le {10}^2$
• 1≤X≤6$1\le X\le 6$

Subtask #3 (85 points): original constraints

Example Input

3
1 2
3 1
2021 42

Example Output

Chef
Divyam 
Divyam

Explanation

Example case 1: Since D=1$D=1$ is divisible by 0$0$ primes, Chef will write 0$0$ and win the game in the first move.

Example case 2: Chef must choose D$D$ between 1$1$ and 5$5$ inclusive since D=6$D=6$ is divisible by more than one prime. Then, Divyam can always choose 6−D$6-D$, write 0$0$ on the board and win the game.

Solution-

Hint-

Do not try to calculate x! .learn sieve of Eratosthenes this problem is related to this topic.

solution will be posted anytime soon.

Join Telegram for update - https://t.me/competitiveProgrammingDiscussion