DCEPC703 - Totient Game
Bahl and Debnath are always looking up for new exciting games on the internet. Yesterday, Bahl stumbled across a new game known as “Totient Game”. He immediately showed that to Debnath. They found it pretty exciting and decided to play it. The game is as follows:
- The game is played with N piles of stones.
- 2 players play alternatively and at each turn a player selects a pile and divides it into two unequal sized piles “i” and “j” such that Totient(i)*Totient(j)=Totient(i*j) and i+j = number of stones in that pile.
- The player who is unable to make a move loses the game.
Bahl insists on starting the game first. Can you predict the winner of the game? Assume that both player plays optimally.
http://en.wikipedia.org/wiki/Euler%27s_totient_function
Input
First line gives T, the number of test cases.
Each test starts with a line containing “N”, the number of piles.
Next line gives N space separated integers. The ith integer represents the number of stones in the ith pile.
Output
Output T lines each containing the winner of the T games. Output “Bahl” if Bahl wins the game or “Debnath” if Debnath wins the game.
Constraints
1<=T<=10
1<=N<=10^5
1<= Number of stones in each pile <=10^7
Example
Input: 1 3 1 2 3 Output: Bahl
hide comments
anonymous:
2023-02-17 23:46:50
Really nice problem!
|
|
sajjad_hm:
2018-04-27 13:41:35
Totient(i)*Totient(j)=Totient(i*j) if gcd(i,j)=1 |
|
[Lakshman]:
2014-05-28 16:08:22
I think all number can be represented in form of Totient(i)*Totient(j)=Totient(i*j) where i+j = n; |
Added by: | dce coders |
Date: | 2012-04-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
Resource: | Own Problem |