-1

The number 1 can be written as sum of fractions of the form 1/p (where p>1). There are different ways to write it. You will be given an integer k which denotes the number of fractions to be used to get the sum as 1. You need to find the largest possible value of p among all possible ways. See sample input for clarity

Input Format:

The first line contains number of test cases t. Then t lines follow each having a single integer k.

Output:

You need to print the largest value of p modulo 10^9 + 7.

Constraints:

1<=t<=10^5
2<=k<=10^6

Sample Input --------------- Sample Output

2                        2
2                        6
3

Explanation There is only one way to write '1' as sum of two fractions. 1/2 + 1/2. hence the largest value is 2. In the second test case, the only possible ways as sum of three fractions are:

1/3, 1/3, 1/3
1/6, 1/2, 1/3
1/4, 1/4, 1/2

Among these the second representation has the largest denominator which is '6' and hence the answer.

Dangling_pointer

Posted 2014-01-17T13:34:29.760

Reputation: 491

Ah, so the trivial solution of p = k is suboptimal. p modulo 10^9 + 7 not sure I get this though – Cruncher – 2014-01-17T13:40:16.360

what does 2 2\n2 6\n3 mean... – mniip – 2014-01-17T13:45:18.977

@mniip the left is input. The right is output. The first input number is the number of cases, so the 2 matches the 2, and the 3 matches the 6. The first 2 just says there's 2 cases. – Cruncher – 2014-01-17T15:08:51.693

wouldn't that be 2\n2 2\n3 6 then? – mniip – 2014-01-17T15:12:22.737

@mniip I can see how it's confusing, but that would imply that the output has to start with a newline. They're 2 separate boxes really, the fact that they're side by side is irrelevant. One is input and one is output – Cruncher – 2014-01-17T15:14:13.260

Answers

Java

I solved this basic problem on Stack Overflow already, so I might as well do it here, too. Follow the link for a deeper explanation of the algorithm, but there's no reason to calculate all the possible fractions if you just want to know the largest denominator.

The only major difference between the code here and on SO is that I'm using modular multiplication, since each result should be mod 10^9 + 7 and this speeds it up considerably.

public class Egyptian {
    static int range = 1000000;
    static long[] mods;
    static long mod = 1000000007;

    public static void main(String[] args){
        mods = new long[range+1];
        mods[1] = 1;
        for(int k=2;k<=range;k++){
            mods[k] = (mods[k-1] * (mods[k-1]+1)) % mod;
            System.out.println(mods[k]);
        }
    }
}

Note: This code simply calculates and outputs every value for inputs 2 to 10^6. As a popularity contest, I thought a simple proof of concept would be enough. Feel free to downvote if you disagree.

It runs in a few seconds, but most of that time is taken by the million-line output. If you just want to fill the array with correct values, it finishes in well under a second. You can then read/write the input/output at the speed of IO.

Output: (only from 2-40, can't exactly paste a million lines here)

Geobits

Posted 2014-01-17T13:34:29.760

Reputation: 19 061

-1

APL (50)

⍪{⌈/∊v/⍨{g=+/(g←∧/⍵)÷⍵}¨v←,∘.,∘v⍣(n-1)⊢v←⍳!n←⎕}¨⍳⎕

This code skips the 'p modulo 10⁹ + 7' computation. But the algorithms is so slow (exponential) that you can barely get a result for k=5, let alone 10⁹. Therefore by all practical means it can be considered equivalent to a piece of code that computed it :-)

Example

      ⍪{⌈/∊v/⍨{g=+/(g←∧/⍵)÷⍵}¨v←,∘.,∘v⍣(n-1)⊢v←⍳!n←⎕}¨⍳⎕
⎕:
      3
⎕:
      2
⎕:
      3
⎕:
      4
 2
 6
24

The ⎕: is just the "input prompt" when used interactively.

Tobia

Posted 2014-01-17T13:34:29.760

Reputation: 5 455

k=4 output should be 42: (1/2 + 1/3 + 1/7 + 1/42) – Geobits – 2014-05-02T17:29:25.223

Largest Denominator

Answers

Java

APL (50)