Nirmit Dalal

Greenhorn

Posts: 22

posted 3 years ago

Recently i tried this problem at CodeChef.This is the Problem Definition.

This is probably the easiest task of this problem set. To help you understand the task let us define two key functions: f(n,k), (with k <= n) which gives the number of ways we can draw a sample of k objects from a set of n-distinct objects where order of drawing is not important and we do not allow repetition. G(x1, x2, x3, ... , xn) is the largest integer that perfectly divides all of {x1, x2, x3, ... , xn}. Given an integer N, your task is to compute the value of Y where Y = G( f(2*N,1), f(2*N,3), f(2*N,5), ... , f(2*N,2*N-1)).

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first and the only line of each test case contains a single integer denoting the given N as described in the problem statement.

Output

For each test case, output a single line containing the value of Y. Constraints

1 ≤ T ≤ 10000 2 ≤ N ≤ 1011

Example

Input: 3 6 5 4 Output: 4 2 8

Now i wrote a code in Java which works perfectly fine but the CodeChef online judge give TLE error, so i tried it a couple of different ways but with no success. So i checked some solution which others had posted and i Didnt have a clue what their algorithm did but magically it always came to the right answer So what my concern is that what books should i refer to improve the way these algorithms are written . P.S. Yes i have read Corman

Some other solution did some normal addition and subtraction and Bang!! their answer were correct This was one such solution

I am also showing what i had attempted :-

okay this question may be subjective but i would really like some suggestion as to where to start from

This is probably the easiest task of this problem set. To help you understand the task let us define two key functions: f(n,k), (with k <= n) which gives the number of ways we can draw a sample of k objects from a set of n-distinct objects where order of drawing is not important and we do not allow repetition. G(x1, x2, x3, ... , xn) is the largest integer that perfectly divides all of {x1, x2, x3, ... , xn}. Given an integer N, your task is to compute the value of Y where Y = G( f(2*N,1), f(2*N,3), f(2*N,5), ... , f(2*N,2*N-1)).

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first and the only line of each test case contains a single integer denoting the given N as described in the problem statement.

Output

For each test case, output a single line containing the value of Y. Constraints

1 ≤ T ≤ 10000 2 ≤ N ≤ 1011

Example

Input: 3 6 5 4 Output: 4 2 8

Now i wrote a code in Java which works perfectly fine but the CodeChef online judge give TLE error, so i tried it a couple of different ways but with no success. So i checked some solution which others had posted and i Didnt have a clue what their algorithm did but magically it always came to the right answer So what my concern is that what books should i refer to improve the way these algorithms are written . P.S. Yes i have read Corman

Some other solution did some normal addition and subtraction and Bang!! their answer were correct This was one such solution

I am also showing what i had attempted :-

okay this question may be subjective but i would really like some suggestion as to where to start from

Maxim Karvonen

Ranch Hand

Posts: 121

12

posted 3 years ago

Hi, Nirmit.

Did you run your code with large numbers for N? Something like 10000 will be sufficient to see a problem.

Anyway, this task is one of "special kind". Solution algorithm is "just calculate the answer" but to calculate that answer you should use some math. As sample input suggests, an answer is some power of two. First solution calculates exactly that although in a very tricky way. Other solutions may calculate required power in more straight-forward way. You definitely does not need to calculate any f or G function. Probably you should prove that "one particular power of two is the answer", but it is not required to provide "acceptable" solution.

As to the math. You should familiar with number theory to solve this task. Can't suggest any books on that (they may be different in different countries). I learnt required theory on a lectures in training camps during my school years. You may took school math contests (regionals or national levels) and Olympiads as a guideline. There are some books with problems and solution. Some other branches of pure mathematics also may be used to create tasks for programming contests (geometry, algebra, calculus). But you don't need anything special except math used in school math contests (though pretty high-level contests) to solve "special" tasks in programming contests.

Did you run your code with large numbers for N? Something like 10000 will be sufficient to see a problem.

Anyway, this task is one of "special kind". Solution algorithm is "just calculate the answer" but to calculate that answer you should use some math. As sample input suggests, an answer is some power of two. First solution calculates exactly that although in a very tricky way. Other solutions may calculate required power in more straight-forward way. You definitely does not need to calculate any f or G function. Probably you should prove that "one particular power of two is the answer", but it is not required to provide "acceptable" solution.

As to the math. You should familiar with number theory to solve this task. Can't suggest any books on that (they may be different in different countries). I learnt required theory on a lectures in training camps during my school years. You may took school math contests (regionals or national levels) and Olympiads as a guideline. There are some books with problems and solution. Some other branches of pure mathematics also may be used to create tasks for programming contests (geometry, algebra, calculus). But you don't need anything special except math used in school math contests (though pretty high-level contests) to solve "special" tasks in programming contests.

posted 3 years ago

And if your number theory skills are limited, it's still worthwhile working your way through some small examples and noting the patterns which appear. Then you can write code which matches the patterns rather than writing code which implements the question in an unsophisticated way.