Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Free Mango

By Aungkur · Limits 1s, 256 MB

Alice has a magical mango garden. There are 10610^6 mango trees. the magically ii-th tree has D(i)D(i) number of mangoes. Here, D(i)D(i) represents the number of the divisors of ii.

Bob wants to buy all the mangoes. Before buying mangoes, Alice offered to Bob that if Bob could answer all the queries correctly, Alice would give the mangoes for free.

Alice will ask QQ queries. Each of them will contain a range [L, R][L,  R]. Now, Alice and Bob will play a game. Alice will make the first move. He will choose a tree from the range [L,R][L, R] and collect mangoes from it as many as he wants. Then Bob will do the same. The person who can't collect any mangoes in his turn loses the game. Bob will have to answer who will win if both of them collect mangoes optimally. (At the beginning of each query, magically the number of mangoes in the ii-th tree will be D(i)D(i))

FYI: Bob gets the mangoes for free. Now, you have to say what was Bob’s answer for each query.


The first line contains a integer Q(1Q105)Q (1 \leq Q \leq 10^5), the number of queries.

Next QQ lines contain two positive integers L,R(1LR106)L, R (1\leq  L\leq R\leq 10^6), denotes the left and the right ends of the corresponding range.


For each query, print “Alice”\texttt{“Alice”}(without quotes) if Bob’s answer was “Alice will win”, otherwise print “Bob”\texttt{“Bob”}(without quotes).


1 3
2 3
3 9



    48% Solution Ratio

    Asad_BinEarliest, 4M ago

    pathanFastest, 0.0s

    YouKnowWhoLightest, 4.6 MB

    YouKnowWhoShortest, 461B


    Login to submit


    Prerequisite: Nim Game (Game Theory), Divisor Sieve (Number Theory) Explanation: At first, we have t...

    Toph uses cookies. By continuing you agree to our Cookie Policy.