Ways to factorise a number

help
1

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 26, 34 and 223. 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
2

Problem Source ?

3

Amazon test series on gfg

4

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.