GOPI_SW - Gopi and Sandwich
Gopi is fond of sandwiches. Once his friend asks him to give part of his sandwich. But, Gopi wants to give him as little sandwich as possible. So, he devices a method.
He divides the sandwich into n parts, where each part is a unit fraction( fractions of the form 1/p where p is integer) of the original sandwich. Among all these parts he chooses the smallest part and gives it to his friend. Help Gopi to find the smallest part possible.
First line contains t(1<=t<=105) the number of test cases. The next t lines contain one integer per line denoting n(2<=n<=106) the number of parts the sandwich can be divided.
Output one line per test case containing the denominator of the smallest part. Since, the answer can be very large, print Answer modulo 109 + 7
3 Output: 6
The possible ways of dividing the sandwich into 3 parts are:
Among these, the second way has the smallest part. Hence the output is 6
use array to prevent urself from tle.... :)
Baqir khan :
Lesson learned, never use both cin/cout and scanf/printf in one program !
simple Egyptian Fractions....green:-)
adhikari vushesh babu:
good question :)
really nice one AC in second attempt.
@rivu das : ans for 10^6 = ***
@nitish: What is the ans for 10^6???
Last edit: 2014-05-27 10:13:43