You are given an integer N. You have to count how many possible combinations of numbers from 1 to N (excluding 1 and N). which are dividing the number N and after multiplication exactly equal to the value N.

For Example: Let suppose, I have a number 12 and the number that divides 12 between 1 to 12 are 2, 3, 4, 6 we can form N by multiply 2*6, 3*4 and 2*2*3. So, there are 3 possible combinations for number 12.

Note: We will not consider 1 and N we will try to find the combinations in between them. Input: First-line contains the T number of test cases.

For each test case, there is an integer N.

Output: Print the number of combinations possible.

Constraints: 1 <= T <= 10, 1 <= N <= 10^6

Example:

Sample

Input:

3

12

8

32

Sample Output:

3

2

6

Explanation: For test case 1: For value 12 we have 3 combinations in total. [ [2, 6], [2, 2, 3], [3, 4] ] For test case 2: For value 8 we have only 2 combinations: [ [2, 2, 2] , [2, 4] ]

Can someone please help me solve this one?

1 Like

Amazon test series on gfg

The problem is same as writing n = d_1d_2..d_k, such that 2 \leq d_1 \leq d_2..\leq d_k. Therefore k \leq log(n). We can therefore write a recursive dp[i][j] which denotes the number of ways to write i as a product of increasing numbers such that minimum number is atleast j. Therefore dp[i][j] = \sum\limits_{k|i, k \geq j}dp[i/k][k]. So, you can pre-compute all the divisors in O(N*log(N)) and then answer for each test case. I am not sure about the complexity but it looks around O(N*log^2(N)) due to maps and divisors.

##
Code

```
#include <bits/stdc++.h>
using namespace std;
vector<int> divi[1000001];
void pre()
{
int i, j;
for(i=2;i<1000001;i++)
for(int j = i; j < 1000001 ; j+=i)
divi[j].push_back(i);
}
map<pair<int, int>, int> dp;
int solve(int n, int j) // divisor >= j
{
if(n == 1)
return 1;
if(j > n)
return 0;
if(j*j > n)
return 1;
if(dp.find({n, j}) != dp.end())
return dp[{n, j}];
int idx = lower_bound(divi[n].begin(), divi[n].end(), j) - divi[n].begin();
int ans = 0;
while(idx < divi[n].size())
{
ans = ans + solve(n/divi[n][idx], divi[n][idx]);
idx++;
}
return (dp[{n, j}] = ans);
}
int main() {
pre();
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
cout << solve(n, 2) - 1 << '\n' ;
}
}
```

Also notice that in dp[i][j] = \sum\limits_{k|i, k \geq j}dp[i/k][k], i/k \geq k or k \leq \sqrt i. Therefore, you can further optimize this approach.

If anyone has a better solution, please share.