xormaxim's blog

By xormaxim, history, 5 years ago, In English

Can anybody provide me any hint on how to solve this problem? The problem is as follows.

The contest in which it was asked is over.

Mr. X is teaching number theory in his class. He is discussing about factors and permutations in his class. A factor of a positive integer N is a positive integer that divides n precisely (without leaving a remainder). The set of factors always includes 1 and N.

Mr. X likes combinatorics a lot. He asked his students find out all the factors of the number Y, and sort them in an ascending order. He asks them to list all permutations of the factors. They then need to cross out all permutations where two adjacent numbers are adjacent in the same order in the original list. The number of uncrossed (valid) permutations are to be given to him.

Illustration:

Integer 9 has 3 factors [1,3,9].

The permutations of these factors of number 9 are [1,3,9],[1,9,3],[3,9,1],[3,1,9],[9,1,3],[9,3,1].

Of these 6 permutations, we need to cross out [1,3,9] (1 3 adjacent in same order), [3,9,1] (3 9 in same order) and[9,1,3] (1 3 in same order)

The remaining (valid) permutations are:

[1,9,3] ,[9,3,1],[3,1,9]

Hence the number of valid permutations =3, which is the answer.

Constraints 1<= N<=120000

1<=T <= 100

Input Format The first line contains T, the number of testcases

Next T lines contain the integer N

Output T lines containing number of valid permutations satisfying conditions mentioned in the problem statement for given input.

Test Case

Explanation Example 1

Input

1

10

Output

11

Explanation

T=1 (there is 1 test case)

N=10.

10 has 4 factors [1,2,5,10]. There are 24 permutations of these four factors. The 11 valid permutations are [1,5,2,10],[1,10,5,2], [2,1,10,5],[2,10,1,5], [2,10,5,1], [5,1,10,2], [5,2,1,10], [5,2,10,1], [10,1,5,2], [10,2,1,5], [10,5,2,1]. Hence the output is 11

Example 2

Input

2

6

9

Output

11

3

Explanation

T=2 (there are 2 test cases).

In the first test case, N=6. 6 has four factors [1,2,3,6]. As in the previous example, there are 11 valid permutations for these. Hence the output for the first test case is 11. This is the first line of the output

In the second test case, N=9. As was shown in the Illustration in the problem statement, thenumber of valid permutations is 3. Hence the output for the second test case (the second line of the output) is 3.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by xormaxim (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

first count total no of factors of given input then ans is in OEIS

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

C++ give wrong ans, python accepted

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    hi, even I appeared for the same contest. The maximum no. of factors for a number would be as big as 144 whose ans will not fit in the long range of some languages.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

why does this formula work ? how to reduce to this formula?

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

First I was generate first few terms using brute force solution then search ON OEIS

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Hi, do you mind providing the problem link, I think I would like to try this problem. Thanks!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It was asked in a mock interview test on the company website so now you can't submit the solution anywhere.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Let's call a pair of numbers in a permutation bad if they are adjacent in the main set, and also let p(n) denote the set of valid permutations of the set {1, 2, .. , n}. We generate the permutations of p(n) in the following manner: 1. Remove n, then for all the valid permutations of the new set, you can add n in any place except exactly one place (immediately after n-1). 2. Remove n, then for each invalid permutation with exactly one bad pair you can add n between them and you obtain a valid permutation.

To see that the set of permutations generated by the previous two steps are the only valid permutations, we prove that p(n) coincide with the above set (let's call it G). Notice that every permutation generated by the above algorithm must be valid, hence G is contained in p(n). Now assume that there exists a permutation in p(n) that is not in G (call it c). Since c is not in G, then if you remove the largest element from c, the resulting permutation has more than one bad pair of numbers. But this means that c originally had at least 1 bad pair of numbers, which is a contradiction.

Now the number of permutations generated by the first step is just (n-1)*|p(n-1)|. The number of permutations generated by the 2nd step is a little trickier. You can generate the permutations of the set {1, .. , n-1} with exactly 1 bad pair by choosing any element x larger than one from it, remove it, obtain all valid permutations of the new set, then stick x on the right of x-1 (then of course put n between them). This can be done in (n-2)|p(n-2)| ways. Hence you obtain the recurrence relation |p(n)| = (n-1)|p(n-1)| + (n-2)|p(n-2)|.

You can simply write a solution that works in linear time to solve the problem.